Ⅰ matlab中如何存儲樹希望提供代碼，萬分感謝，本人編程涉及到剪枝
MATLAB里沒有指針。但是考慮到樹只是圖的一種特例，LZ可以考慮用圖的存儲策略，用鄰接矩陣保存樹是不需要指針的，而且MATLAB對矩陣運算比較效率。就是浪費點空間而已。
Ⅱ 怎樣將一棵二叉樹的存儲結構轉化為一個無向圖的存儲結構，誰能說說編程思想啊
圖的存儲機構一般用鄰接矩陣或鄰接表,二叉樹一般是鏈表結構,就是把鏈表變成臨近矩陣了,用中序形勢對鏈表節點進行編號和訪問並做為臨近矩陣的順序,用中序訪問,對當前節點和後繼節點判斷,然後置對應的矩陣為1,(a[當前],[後繼]=1 ,a[後繼],[當前]=1 ) ,中序訪問完就可以了
Ⅲ 數據結構 ~~~~~最小生成樹問題
/* 用鄰接矩陣表示的圖的prim演算法的源程序*/
#include<stdio.h>
#define MAXVEX 6
typedef char VexType;
typedef float AdjType;
typedef struct {
int n;
/* 圖的頂點個數 */
/*VexType vexs[MAXVEX];
頂點信息 */
AdjType arcs[MAXVEX][MAXVEX];
/* 邊信息 */
} GraphMatrix;
typedef struct{
int start_vex, stop_vex;
/* 邊的起點和終點 */
AdjType weight;
/* 邊的權 */
} Edge;
Edge mst[5];
#define MAX 1e+8
void prim(GraphMatrix * pgraph, Edge mst[]) {
int i, j, min, vx, vy;
float weight, minweight; Edge edge;
for (i = 0; i < pgraph->n-1; i++) {
mst[i].start_vex = 0;
mst[i].stop_vex = i+1;
mst[i].weight = pgraph->arcs[0][i+1];
}
for (i = 0; i < pgraph->n-1; i++) {
/* 共n-1條邊 */
minweight = MAX; min = i;
for (j = i; j < pgraph->n-1; j++)/* 從所有邊(vx,vy)(vx∈U,vy∈V-U)中選出最短的邊 */
if(mst[j].weight < minweight) {
minweight = mst[j].weight;
min = j;
}
/* mst[min]是最短的邊(vx,vy)(vx∈U, vy∈V-U)，將mst[min]加入最小生成樹 */
edge = mst[min];
mst[min] = mst[i];
mst[i] = edge;
vx = mst[i].stop_vex;
/* vx為剛加入最小生成樹的頂點的下標 */
for(j = i+1; j < pgraph->n-1; j++) { /* 調整mst[i+1]到mst[n-1] */
vy=mst[j].stop_vex; weight = pgraph->arcs[vx][vy];
if (weight < mst[j].weight) {
mst[j].weight = weight;
mst[j].start_vex = vx;
}
}
}
}
GraphMatrix graph = {
6,
{{0,10,MAX,MAX,19,21},
{10,0,5,6,MAX,11},
{MAX,5,0,6,MAX,MAX},
{MAX,6,6,0,18,14},
{19,MAX,MAX,18,0,33},
{21,11,MAX,14,33,0}
}
};
int main(){
int i;
prim(&graph,mst);
for (i = 0; i < graph.n-1; i++)
printf("(%d %d %.0f)\
", mst[i].start_vex,
mst[i].stop_vex, mst[i].weight);
return 0;
}
Ⅳ 編程實現以鄰接表或鄰接矩陣為存儲結構，圖的廣度和深度優先搜索
/*******************************************
圖的遍歷演示
以鄰接多重表為存儲結構,實現連通無向圖的深度優先和廣度優先遍歷.
以用戶指定的結點為起點,分別輸出每種遍歷下的結點訪問序列和相應生成樹的邊集.
*******************************************/
#include<iostream>
# include <string.h>
# include <malloc.h>
# include <conio.h>
using namespace std;
int visited[30];
# define MAX_VERTEX_NUM 30
# define OK 1
//typedef int VertexType;
typedef int InfoType;
typedef struct ArcNode //弧
{
int adjvex;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode//表頭
{
int data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct//圖
{
AdjList vertices;
int vexnum,arcnum;
int kind;
}ALGraph;
void CreateDG(ALGraph &G)
{
int k,i,v1;
cout<<endl<<"請輸入結點個數: ";
cin>>G.vexnum;
cout<<"請輸入弧的個數: ";
cin>>G.arcnum;
for(i=1;i<=G.vexnum;i++)//初使化表頭
{
G.vertices[i].data=i;
G.vertices[i].firstarc=NULL;
}
for(k=1;k<=G.vexnum;k++) //輸入邊
{
int v2;
cout<<"請輸入與結點"<<k<<"相鄰的邊數:";
cin>>v2;
cout<<"請輸入與第"<<k<<"個結點相連的結點編號: ";
cin>>v1;
ArcNode *p;
p=(ArcNode*)malloc(sizeof(ArcNode));
if(!p) exit(-1);
p->adjvex=v1;
p->nextarc=NULL;
G.vertices[k].firstarc=p;
for(int i=1;i<v2;i++)
{
int m;
cout<<"請輸入與第"<<k<<"個結點相連的結點編號: ";
cin>>m;
ArcNode *q;
q=(ArcNode *)malloc(sizeof(ArcNode));//動態指針
if(!q) exit(-1);
q->adjvex=m; //頂點給P
q->nextarc=NULL;
p->nextarc=q;
p=q;
//free(q);
}
//free(p);
}
}
void DFS (ALGraph G,int v )//深度搜索
{
visited[v]=1;
cout<<G.vertices[v].data<<" ";
ArcNode *x;
x=(ArcNode*)malloc(sizeof(ArcNode));
if(!x) exit(-1);
x=G.vertices[v].firstarc;
int w;
for (;x;x=x->nextarc)
{ w=x->adjvex;
if(visited[w]==0)
DFS(G,w);
}
}
void DFSB (ALGraph G,int v)//深度搜索的邊集
{
visited[v]=1;
ArcNode *y;
y=(ArcNode*)malloc(sizeof(ArcNode));
if(!y) exit(-1);
y=G.vertices[v].firstarc;
int u=G.vertices[v].data;
int w;
for(;y;y=y->nextarc)
{ w=y->adjvex;
if(visited[w]==0)
{
cout<<u<<"--->"<<w<<endl;
DFSB(G,w);
}
}
}
typedef struct QNode
{
int data;
QNode *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
void InitQueue (LinkQueue &Q)//建立一個空隊列
{
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front) exit(-1);
Q.front->next=NULL;
}
void EnQueue (LinkQueue &Q,int e)//進隊
{
QNode *p;
p=(QNode*)malloc(sizeof(QNode));
if(!p) exit(-1);
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
//free(p);
}
int DeQueue (LinkQueue &Q,int &e)//出隊
{
if(Q.front==Q.rear)
return -1;
QNode *p;
p=(QNode*)malloc(sizeof(QNode));
if(!p) exit(-1);
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)
Q.rear=Q.front;
free(p);
return e;
}
int QueueEmpty (LinkQueue Q)//判斷隊列是否為空
{
if(Q.front==Q.rear)
return 1;
return 0;
}
void BFS(ALGraph G,int v)//廣度搜索
{
int u;
LinkQueue Q;
InitQueue(Q);
if(visited[v]==0)
{
visited[v]=1;
cout<<G.vertices[v].data<<" ";
EnQueue(Q,v);
while(QueueEmpty(Q)!=1)
{
DeQueue(Q,u);
ArcNode *z;
z=(ArcNode*)malloc(sizeof(ArcNode));
if(!z) exit(-1);
z=G.vertices[u].firstarc;
/*
for(int w=z->adjvex;w>=0;w=z->nextarc->adjvex)
{
if(visited[w]==0)
{
visited[w]=1;
cout<<w<<" ";
EnQueue(Q,w);
}
}*/
int w;
for(;z;z=z->nextarc)
{ w=z->adjvex;
if(visited[w]==0)
{
visited[w]=1;
cout<<w<<" ";
EnQueue(Q,w);
}
}
}
}
}
void BFSB (ALGraph G,int v)//廣度搜索的邊集
{
int u;
LinkQueue Q;
InitQueue(Q);
if(visited[v]==0)
{
visited[v]=1;
EnQueue(Q,v);
while(QueueEmpty(Q)!=1)
{
DeQueue(Q,u);
ArcNode *r;
r=(ArcNode*)malloc(sizeof(ArcNode));
if(!r) exit(-1);
r=G.vertices[u].firstarc;
int w;
for(;r!=NULL;r=r->nextarc)
{ w=r->adjvex;
if(visited[w]==0)
{
visited[w]=1;
cout<<u<<"--->"<<w<<endl;
EnQueue(Q,w);
}
}
}
}
}
int main()
{
int i;
ALGraph G;
CreateDG(G);
int x;
cout<<"請輸入結點數:";
cin>>x;
cout<<"鄰接表為："<<endl;
for(int j=1;j<=x;j++)
{
cout<<G.vertices[j].data<<" ";
ArcNode *p;
p=(ArcNode*)malloc(sizeof(ArcNode));
if(!p) exit(-1);
p=G.vertices[j].firstarc;
while(p)
{
cout<<p->adjvex<<" ";
p=p->nextarc;
}
cout<<endl;
}
cout<<"請輸入第一個要訪問的結點序號："<<endl;
int n;
cin>>n;
for( i=0;i<30;i++)
visited[i]=0;
cout<<"廣度搜索："<<endl;
BFS(G,n);
for( i=0;i<30;i++)
visited[i]=0;
cout<<endl;
cout<<"邊集："<<endl;
BFSB(G,n);
for( i=0;i<30;i++)
visited[i]=0;
cout<<"深度搜索："<<endl;
DFS(G,n);
for( i=0;i<30;i++)
visited[i]=0;
cout<<endl;
cout<<"邊集："<<endl;
DFSB(G,n);
//system("pause");
return 0;
}
前幾天上機剛好做了這個,個人感覺很完美,盡管老師說用的是鄰接表而不是多重表,太簡單,但還不錯,界面輸入過程比較繁瑣,要嚴格按照提示來輸入,是無向圖,等級太低,沒辦法把執行結果粘出來,應該能看懂吧
Ⅳ 有些圖論題數據太大無法用鄰接矩陣，所以請教教我怎麼用數組模擬鄰接表建圖（帶權）。（C/C++代碼）
暫且與例題一起的
路徑(netbar.pas)
綿陽中學以人數眾多而聞名。三個年級共有 10000 多人，學生多了附近的網吧也多。
Mzoiers 都熱衷於 Dota，可學校的機子配置相當差(評測伺服器除外)，根本不能玩
Dota，那就只有去網吧。星期天到星期五都是晚上 10：20 才下晚自習，幾乎沒時間玩。
然而星期六下午放假是絕好的時間，但是學校人多啊，一放學去網吧的人就開始狂奔，競爭
之激烈，搶到機子的難度非常之大。往往在我們到達網吧之前都坐滿了。
學校到網吧的路是錯綜復雜的，以致於到一個自己想去的網吧都有非常多的路線可以選
擇，而路線的長度又不相同，這樣就決定了要花費的時間，因此想要盡快到達，選擇一條最
佳的線路是很有必要的。
【問題描述】
為了簡化問題，我們把學校與周邊的網吧看做圖中的頂點，學校與網吧，網吧與網吧之
間的路線看做邊，每個邊都有一個權，表示我們走完這條路的時間，由於放學人流量大，如
果反向走會有危險，因此這是一個有向圖。
我的學校在 S 點，想要去的網吧在 T 點。你的任務就是選擇一條最佳路線，使得從
學校到目的地網吧的時間最短，你只需要輸出最短到達時間即可。
【輸入文件】
netbar.in 中共有 M+2 行數據
第一行兩個整數 N，M，表示點數和邊數。
然後 M 行每行 3 個正整數(u，v，t)，表示有一條可由 u 到 v 耗時為 t 的邊。
最後一行兩個正整數 S、T。
【輸出文件】
netbar.out 中，只有一行，一個整數表示最短時間。如果 S、T 之間不存在通路則輸
出「No Solution!」(雙引號不輸出，「!」為西文標點)。
【輸入樣例】
4 4
1 2 3
2 4 10
1 3 5
3 4 5
1 4
【輸出樣例】
10
【數據規模】
對於 30％的數據保證有 1<N<=1000，1<=M<=1000；
對於全部的數據保證有 1<N<=10000，1<=M<=100000。
解題思路：
題目可以抽象為輸入n個頂點，e條邊的有向圖，再讀入源點S和目標點T，求S到T的最短路。輸入規模：1<N<=10000，1<=M<=100000。
最短路有三種方法：floyd,dijsktra,spfa。如果用floyd,時間性能為O(n3) , 只能通過1000以內的數據；用dijkstra，時間性能為O(n2) ，只能通過10000以內的數據，且用鄰接矩陣存儲時，10000*10000*4個位元組，總內存達到380多MB，會超內存。用spfa演算法，時間性能為O(kM)，能通過所有測試數據，k的值平均為2，表示頂點入隊的平均次數。此時，可以採用數組模擬鏈表的存邊方法，開一個邊的一維數組，把所有邊存儲起來。如對於如下輸入數據：
5 7
1 2 2
1 5 8
1 3 1
1 4 3
2 5 3
3 5 1
4 3 2
1 5
下面這個圖的數組模擬鏈表的形式存儲邊，把從某個頂點出來的所有邊通過鏈表的形式，鏈接起來，就象存儲普通有序樹一樣，右兒子掛到左兒子下面。這里的操作原理是，處理某個頂點出來的邊時，下一條邊掛到前一條邊，如下圖，第一條邊指向0，後面的邊都指向前一條邊，所以，在處理某個頂點相連的邊的松馳操作時，可以很方便的處理以該頂點連出去的邊，當指向0時，則以該 頂點出去的松馳操作完成。
program netbar;
var
list,dis:array [0..10000] of longint; //list存儲當前邊的指針,dis存儲各點到源點的最短路
next,toit,cost,q:array [0..100000] of longint;//next存儲當前邊指向前一條邊的位置，toit表示當前邊的出點，cost表示當前邊的邊權
n,m,i,a,b,c,s,e,tot:longint;
flag:array [0..10000] of boolean;
procere add(a,b,c:longint);//數組模擬鏈表的添邊的方法
begin
inc(tot); //邊的數目
toit[tot]:=b; //當前邊的出點頂點標號
cost[tot]:=c; //當前邊的權值
next[tot]:=list[a]; //當前邊指向前一條邊的位置，如果當前邊是頂點a的讀入的第一條邊，則它指向前面第0條邊，表示next[tot]:=0。
list[a]:=tot; //從入點a引出的邊的編號存儲給lsit[a]
end;
procere SPFA;
var
i,head,tail,v,k:longint;
begin
fillchar(flag,sizeof(flag),true);
for i:=1 to n do dis[i]:=maxlongint;
head:=1; tail:=1; q[1]:=s; dis[s]:=0; flag[s]:=false;//源點s入隊
repeat
v:=q[head]; k:=list[v]; //隊列頭出隊，k存儲當前v頂點的邊的編號
while k<>0 do //處理v的所有邊，直至邊指向0，即第一條邊也處理了
begin
if dis[v]+cost[k]<dis[toit[k]] then //松馳操作
begin
dis[toit[k]]:=dis[v]+cost[k]; //松馳成功
if flag[toit[k]] then //入隊
begin
inc(tail); q[tail]:=toit[k]; flag[toit[k]]:=false;
end;
end;
k:=next[k]; //處理頂點v的前一條邊
end;
flag[v]:=true;
inc(head);
until head>tail;
end;
begin
assign(input,'netbar.in'); reset(input);
assign(output,'netbar.out'); rewrite(output);
fillchar(list,sizeof(list),0);
fillchar(next,sizeof(next),0);
fillchar(toit,sizeof(toit),0);
fillchar(cost,sizeof(cost),0);
tot:=0;
readln(n,m);
for i:=1 to m do
begin readln(a,b,c); add(a,b,c); end;
readln(s,e);
SPFA;
if dis[e]<maxlongint then writeln(dis[e])
else writeln('No Solution!');
close(input); close(output);
end.
當N的頂點規模達到10000時，如果用鄰接矩陣存儲圖，容易超內存，且1個億的運算次數在1S的時限內不一定出得來。
不好意思 這邊只有PASCAL 的 暫且將就吧 c語言的MS沒有額……
Ⅵ 數據結構，如何根據鄰接表畫深度，廣度優先生成樹
深搜中枚舉時由大到小就是這個結果。
#include"stdio.h"
#include"stdlib.h"
#define MaxVertexNum 100 //定義最大頂點數
typedef struct{
char vexs[MaxVertexNum]; //頂點表
int edges[MaxVertexNum][MaxVertexNum]; //鄰接矩陣，可看作邊表
int n,e; //圖中的頂點數n和邊數e
}MGraph; //用鄰接矩陣表示的圖的類型
//=========建立鄰接矩陣=======
void CreatMGraph(MGraph *G)
{
int i,j,k;
char a;
printf("Input VertexNum(n) and EdgesNum(e): ");
scanf("%d,%d",&G->n,&G->e); //輸入頂點數和邊數
scanf("%c",&a);
printf("Input Vertex string:");
G->vexs[i]=a; //讀入頂點信息，建立頂點表
}
for(i=0;i<G->n;i++)
for(j=0;j<G->n;j++)
G->edges[i][j]=0; //初始化鄰接矩陣
printf("Input edges,Creat Adjacency Matrix ");
for(k=0;k<G->e;k++) { //讀入e條邊，建立鄰接矩陣
scanf("%d%d",&i,&j); //輸入邊（Vi，Vj）的頂點序號
G->edges[i][j]=1;
G->edges[j][i]=1; //若為無向圖，矩陣為對稱矩陣；若建立有向圖，去掉該條語句
}
//=========定義標志向量，為全局變數=======
typedef enum{FALSE,TRUE} Boolean;
Boolean visited[MaxVertexNum];
//========DFS：深度優先遍歷的遞歸演算法======
void DFSM(MGraph *G,int i)
visited[i]=TRUE; //置已訪問標志
for(j=0;j<G->n;j++) //依次搜索Vi的鄰接點
if(G->edges[i][j]==1 && ! visited[j])
DFSM(G,j); //（Vi，Vj）∈E，且Vj未訪問過，故Vj為新出發點
void DFS(MGraph *G)
{
int i;
for(i=0;i<G->n;i++)
visited[i]=FALSE; //標志向量初始化
for(i=0;i<G->n;i++)
if(!visited[i]) //Vi未訪問過
DFSM(G,i); //以Vi為源點開始DFS搜索
}
//==========main=====
void main()
{
//int i;
MGraph *G;
G=(MGraph *)malloc(sizeof(MGraph)); //為圖G申請內存空間
CreatMGraph(G); //建立鄰接矩陣
printf("Print Graph DFS: ");
DFS(G); //深度優先遍歷
printf(" ");
}
(6)樹可以用鄰接矩陣存儲擴展閱讀：
圖的鄰接表存儲方法跟樹的孩子鏈表示法相類似，是一種順序分配和鏈式分配相結合的存儲結構。如這個表頭結點所對應的頂點存在相鄰頂點，則把相鄰頂點依次存放於表頭結點所指向的單向鏈表中。
如詞條概念圖所示，表結點存放的是鄰接頂點在數組中的索引。對於無向圖來說，使用鄰接表進行存儲也會出現數據冗餘，表頭結點A所指鏈表中存在一個指向C的表結點的同時，表頭結點C所指鏈表也會存在一個指向A的表結點。
Ⅶ 存儲圖時，哪些情況用鄰接矩陣方便
如果邊比較少的情況下，用鄰接矩陣節省存儲空間。邊比較多就可以選擇鄰接矩陣
Ⅷ 求無向連通圖的生成樹（用c語言設計程序）
不知道你要的是不是這個 完整實現如下： #define INFINITY 65535typedef int status;# include <stdio.h># include <stdlib.h># include <conio.h># include "string.h"# define maxlen 10typedef struct{ char vexs[maxlen][maxlen];/*頂點信息集合,我們用它來存入頂點名字*/ int vexnum,arcnum;/*頂點數和邊數*/ int arcs[maxlen][maxlen];/*鄰接矩陣*/}graph;//定位輸入節點的名稱int LocateVex(graph G,char u[maxlen]){int i;for(i=0;i<G.vexnum;++i) if(strcmp(u,G.vexs[i])==0) return i; return -1;} void prim(graph &g)/*最小生成樹*/{ int i,j,k,min,w,flag; int lowcost[maxlen];/*權值*/ int closet[maxlen];/*最小生成樹結點*/ char va[maxlen],vb[maxlen]; //初始化鄰接矩陣 //printf("請輸入頂點數和邊數：\n"); //scanf("%d%d",&g.vexnum,&g.arcnum); g.vexnum=6; g.arcnum=10; printf("請輸入頂點信息(我們這里指名字)：\n"); for(int j=0;j<g.vexnum;j++) scanf("%s",g.vexs[j]); for(i=0;i<g.vexnum;++i) for(j=0;j<g.vexnum;++j)//初始化鄰接矩陣 { g.arcs[i][j]=INFINITY; //任意兩個頂點間距離為無窮大。 }//for /*printf("請輸入%d條弧的弧尾 弧頭 權值（以空格為間隔)\n",g.arcnum); for(k=0;k<g.arcnum;++k) { scanf("%s%s%d%*c",va,vb,&w);//用%*c吃掉回車符 i=LocateVex(g,va); //注意，這里定義的是char va[5]，也就是說va是首地址 j=LocateVex(g,vb); g.arcs[i][j]=w; //無向網 g.arcs[j][i]=w; //無向網 }//for */ g.arcs[0][1]=6; g.arcs[1][0]=6; g.arcs[0][2]=1; g.arcs[2][0]=1; g.arcs[0][3]=5; g.arcs[3][0]=5; g.arcs[1][2]=5; g.arcs[2][1]=5; g.arcs[1][4]=3; g.arcs[4][1]=3; g.arcs[2][3]=5; g.arcs[3][2]=5; g.arcs[2][4]=6; g.arcs[4][2]=6; g.arcs[2][5]=4; g.arcs[5][2]=4; g.arcs[3][5]=2; g.arcs[5][3]=2; g.arcs[4][5]=6; g.arcs[5][4]=6; printf("最小生成樹的邊為:\n"); for(i=1;i<g.vexnum;i++) { lowcost[i]=g.arcs[0][i]; closet[i]=1; } closet[0]=0; //初始v1是屬於集合U的，即設它是最小生成樹中節點的一員 j=1; //V是頂點集合 for(i=1;i<g.vexnum;i++) { min=lowcost[j]; k=i; for(j=1;j<g.vexnum;j++) if(lowcost[j]<min&&closet[j]!=0) { min=lowcost[j]; k=j; //記錄當前要加入集合U的節點號 }//if if(i==1) flag=0; else flag=closet[k]; //還沒有加入集合U的節點的closet[]值是 //記錄了上一次加入集合U的節點號 closet[k]=0; //將剛剛找到的點加入到集合U中 printf("(%s,%s),",g.vexs[k],g.vexs[flag]);//輸出剛剛找到的最小生成樹樹枝 for(j=1;j<g.vexnum;j++) if(g.arcs[k][j]<lowcost[j]&&closet[j]!=0) { lowcost[j]=g.arcs[k][j]; //更新lowcost[]的值，且在還沒有加入U集合的 //的closet[]中記錄剛剛加入U集合的節點號以備 //下一循環中輸出用 closet[j]=k; } }} int main(){graph g;prim(g);}