首頁 > 資訊 > 知識 > 鄰接表，圖的鄰接表

鄰接表，圖的鄰接表

來源：整理時間：2025-05-11 08:53:45 編輯：智能門戶手機(jī)版

本文目錄一覽

1，圖的鄰接表
2，有向圖用鄰接表如何表示不是程序表示求其詳細(xì)的過程
3，如何建立鄰接表
4，基于鄰接表建圖的幾種方法
5，鄰接表做深度優(yōu)先遍歷和廣度優(yōu)先遍歷的代碼

1，圖的鄰接表

1.可以。2.如果a->b和b->a均在鄰接表里成對存在，則是無向圖的鄰接表，否則是有向圖的鄰接表。a和b是圖中頂點。

圖的鄰接表

2，有向圖用鄰接表如何表示不是程序表示求其詳細(xì)的過程

第一步：觀察圖有多少頂點，這里，ABCDE有5個，就劃5個頂點的，數(shù)組，并在旁邊編號01234。第二步：從上到下，依次觀察ABCDE這5個結(jié)點，首先A結(jié)點，它發(fā)出2條邊B,D，所以把它的指針首先隨便指向一個B或者D的編號，這里指向D，因為D的編號是3，然后指向另外的沒有指向的編號B,就是了。最后沒有邊的，指向就是空指針。第三步：依次按照A點的方法，寫出BCDE點的指向的邊的編號，沒有就用空表示。理解的關(guān)鍵。鄰接表數(shù)據(jù)的那個頂點和后面指向的編號的結(jié)點，這兩個點的意思和寫法不同，數(shù)組的表示的存儲的具體的結(jié)點信息，后邊的表示它發(fā)出的鄰近結(jié)點的編號，沒有其他的結(jié)點信息。

節(jié)點編號：A~E依次編為0~4：從A點（0）出發(fā)的箭頭有2根，分別指向B（1）、D（3）節(jié)點，用節(jié)點號表示為一個鏈表；其他節(jié)點只有一個出邊，也是用目標(biāo)節(jié)點的編號表示。

1.可以。2.如果a->b和b->a均在鄰接表里成對存在，則是無向圖的鄰接表，否則是有向圖的鄰接表。a和b是圖中頂點。

有向圖用鄰接表如何表示不是程序表示求其詳細(xì)的過程

3，如何建立鄰接表

const n=10; e=20; type edge=^edgenode; edgenode=record adj:1..n; weight:integer; next:edge; end; vex=record data:integer; lind:edge; end;var s:edgenode; g=array [1..n] of vex;begin read(n,e); for i:=1 to n do begin read(g[i].data); g[i].link:=nil; end; for k:=1 to e do begin read(i,j,w); new(s); s^.adj:=j; s^.weight:=w; s^.next:=g[i].link; g[i].link:=s; end;end.

鄰接表是一個指針數(shù)組，數(shù)組的每一個元素指向一個鏈表。比如，在某個圖中，點2與點3、點6之間有邊，則鄰接表的元素a[2]指向一個鏈表，該鏈表有2個節(jié)點，其數(shù)據(jù)域分別為3，6

如何建立鄰接表

4，基于鄰接表建圖的幾種方法

數(shù)據(jù)結(jié)構(gòu)書上表示鄰接表比較復(fù)雜，一般形式如下： typedef struct NodeDataType data; //結(jié)點的一些數(shù)據(jù)，比如名字 int sorce; //鄰接邊的弧尾結(jié)點序號 Edge *adj; //鄰接邊頭指針}AdjHeight; //數(shù)組的數(shù)據(jù)元素類型的結(jié)構(gòu)體typedef structAdjHeight a[MaxVertices]; //鄰接表數(shù)組 int numOfVerts; //結(jié)點個數(shù) int numOfEdges; //邊個數(shù)}AdjGraph; //鄰接表結(jié)構(gòu)體其實有種簡潔且高效的表示形式： typedef structint pre[MAX];//初始化memset(pre,-1,sizeof(pre));//輸入scanf("%d %d %d",&from,&to,&w1);e[i].to = to; e[i].w = w1; e[i].next = pre[from]; pre[from] = i;i++; 上面這段代碼中，邊的結(jié)構(gòu)體Edge由三個元素組成：弧頭結(jié)點序號，邊權(quán)值，下一條邊的序號。e[i]指的是第i條邊。pre[i]記錄的是從當(dāng)前輸入的情況來看，序號為i的弧尾結(jié)點發(fā)出的第一條邊的序號是pre[i]。這樣，在操作某個結(jié)點發(fā)出的邊時，可以像這么做： /*now為弧尾結(jié)點序號，i為now所發(fā)出的邊序號，adj為弧頭結(jié)點序號，w為now-->adj這條邊的權(quán)值*/for(i = pre[now]; i != -1; i = edge[i].next)int w = edge[i].w;//do something...} 其實，對于哈希表這類的存儲結(jié)構(gòu)(鏈表法解決沖突)，與圖的鄰接表類似，也可以用類似的表示方法： typedef structchar e[11]; //value char f[11]; //key int next; //下一個結(jié)果(hash沖突)}Entry;Entry entry[M];int hashIndex[M]; //哈希值為M的結(jié)果集的第一個在entry中的序號。

5，鄰接表做深度優(yōu)先遍歷和廣度優(yōu)先遍歷的代碼

3、廣度優(yōu)先搜索算法 (1)鄰接表表示圖的廣度優(yōu)先搜索算法 void BFS(ALGraph*G，int k) int i； CirQueue Q； //須將隊列定義中DataType改為int EdgeNode *p； InitQueue(&Q)；//隊列初始化 //訪問源點vk printf("visit vertex：％e"，G->adjlist[k].vertex)； visited[k]=TRUE； EnQueue(&Q，k)；//vk已訪問，將其人隊。（實際上是將其序號人隊） while(!QueueEmpty(&Q))i=DeQueue(&Q)； //相當(dāng)于vi出隊 p=G->adjlist[i].firstedge； //取vi的邊表頭指針 while(p)if(!visited[p->adivex])printf("visitvertex：％c"，C->adjlistlp->adjvex].vertex)； //訪問vj visited[p->adjvex]=TRUE； EnQueue(&Q，p->adjvex)；//訪問過的vj人隊 }//endif p=p->next；//找vi的下一鄰接點 }//endwhile }//endwhile }//end of BFS （2）鄰接矩陣表示的圖的廣度優(yōu)先搜索算法 void BFSM(MGraph *G，int k) int i，j； CirQueue Q； InitQueue(&Q)； printf("visit vertex：％c"，G->vexs[k])； //訪問源點vk visited[k]=TRUE； EnQueue(&Q，k)； while(!QueueEmpty(&Q))i=DeQueue(&Q)； //vi出隊 for(j=0;j<G->n;j++)//依次搜索vi的鄰接點vj if(G->edges[i][j]==1&&!visited[j])printf("visit vertex：％c"，G->vexs[j])；//訪問vi visited[j]=TRUE； EnQueue(&Q，j)；//訪問過的vi人隊 } }//endwhile }//BFSM

（1）圖的建立，按采用鄰接表作為存儲結(jié)構(gòu)。（2）從指定頂點出發(fā)進(jìn)行深度優(yōu)先搜索遍歷。（3）從指定頂點出發(fā)進(jìn)行廣度優(yōu)先搜索遍歷。#include"stdio.h"#include"string.h"#include"stdlib.h"#include"math.h"#define max_int 1000#define max_vertex_num 20#define max_queue_number 20typedef struct arcnode int adjvex; double adj; struct arcnode *nextarc;}arcnode;typedef struct vexnode char szname[40]; arcnode *firstarc;}vexnode,adjlist[max_vertex_num];typedef struct adjlist vexs; int vexnum,arcnum;}net;//定義隊列typedef struct int *elem; int front, rear;}queue;void initqueue(queue &q) q.elem = new int[max_queue_number]; q.front = q.rear = 0;}int emptyqueue(queue q) if(q.front==q.rear) return 0; else return 1;}void destroyqueue(queue &q) delete []q.elem; q.front = q.rear = 0;}void enterqueue(queue &q, int e) if((q.rear + 1)%max_queue_number != q.front) q.elem[q.rear ] = e; else printf("隊列滿!\n"); q.rear = (q.rear + 1)%max_queue_number;}void leavequeue(queue &q, int &e) if(q.rear != q.front) e = q.elem[q.front]; else printf("隊列空!\n"); q.front = (q.front+1)%max_queue_number;}int locatevex(net ga,char *name) int i; for(i=0;i if(strcmp(name,ga.vexs[i].szname)==0) return i; return -1;}void crt_net(net &ga) arcnode *p; char name1[40],name2[40]; int i,j,k; double w; printf("請輸入頂點數(shù)和弧數(shù)："); scanf("%d%d",&ga.vexnum,&ga.arcnum); printf("請依次輸入頂點名：\n"); for(i=0;i scanf("%s",ga.vexs[i].szname); ga.vexs[i].firstarc=null; } for(k=0;k printf("請輸入相鄰的兩個定點和權(quán)值："); scanf("%s%s%lf",name1,name2,&w); i=locatevex(ga,name1); j=locatevex(ga,name2); p=new arcnode; p->adjvex=j; p->adj=w; p->nextarc=ga.vexs[i].firstarc; ga.vexs[i].firstarc=p; }}void dfs(net ga,char *name,int *visited) int v,w; arcnode *p; v=locatevex(ga,name); visited[v]=1; printf("%s ",ga.vexs[v].szname); p=ga.vexs[v].firstarc; while(p!=null) w=p->adjvex; if(visited[w]==0) dfs(ga,ga.vexs[w].szname,visited); p=p->nextarc; }}void dfstravel(net ga,char *name) int v,k=0; int visited[20]; for(v=0;v visited[v]=0; for(v=locatevex(ga,name);k!=2;v=(v+1)%(ga.vexnum-1)) if(v+1==locatevex(ga,name)) k++; if(visited[v]==0) dfs(ga,ga.vexs[v].szname,visited); }}void bfstravel(net ga,char *name) arcnode *p; int v,w,u,k=0; queue q; int visited[20]; for(v=0;v visited[v]=0; initqueue(q); for(v=locatevex(ga,name);k!=2;v=(v+1)%(ga.vexnum-1)) if(v+1==locatevex(ga,name)) k++; if(visited[v]==0) visited[v]=1; printf("%s ",ga.vexs[v].szname); enterqueue(q,v); while(emptyqueue(q)!=0) leavequeue(q,u); p=ga.vexs[u].firstarc; while(p!=null) w=p->adjvex; if(visited[w]==0) printf("%s ",ga.vexs[w].szname); visited[w]=1; enterqueue(q,w); } p=p->nextarc; } } } }}void main() char name[40]; net ga; crt_net(ga); printf("請輸入深度優(yōu)先遍歷開始點的名："); scanf("%s",name); printf("深度優(yōu)先遍歷："); dfstravel(ga,name); printf("\n"); printf("請輸入廣度優(yōu)先遍歷開始點的名："); scanf("%s",name); printf("廣度優(yōu)先遍歷："); bfstravel(ga,name); printf("\n");}