圖的鄰接表表示法類似于樹的孩子鏈表表示法。對于圖G中的每個頂點vi，該方法把所有鄰接于vi的頂點vj鏈成一個帶頭結點的單鏈表，這個單鏈表就稱為頂點vi的鄰接表(Adjacency List)。

1． 鄰接表的結點結構

（1）表結點結構
? ??┌────┬───┐?
? ??│adjvex??│next??│
? ? └────┴───┘
? ? 　鄰接表中每個表結點均有兩個域:
　① 鄰接點域adjvex
　　存放與vi相鄰接的頂點vj的序號j。
　② 鏈域next
　　將鄰接表的所有表結點鏈在一起。
??注意：
　? ? 若要表示邊上的信息(如權值)，則在表結點中還應增加一個數據域。

（2）頭結點結構
? ??┌────┬─────┐?
? ??│vertex??│firstedge │
? ? └────┴─────┘
? ? 　頂點vi鄰接表的頭結點包含兩個域：
　① 頂點域vertex
　　存放頂點vi的信息
　② 指針域firstedge
　　vi的鄰接表的頭指針。
??注意：
　? ? ① 為了便于隨機訪問任一頂點的鄰接表，將所有頭結點順序存儲在一個向量中就構成了圖的鄰接表表示。
? ? 　② 有時希望增加對圖的頂點數及邊數等屬性的描述，可將鄰接表和這些屬性放在一起來描述圖的存儲結構。

2.代碼實例

#include<iostream> using namespace std; #define MAX_VERTEX_NUM 50//定義圖的最大頂點數 typedef char VertexData; typedef struct EdgeNode//表結點 { int adjvex;//鄰接點域 VertexData data; EdgeNode *next;//邊結點所對應的下一個邊結點 } EdgeNode; typedef struct VertexNode//頭結點 { VertexData data; EdgeNode *firstedge;//頭結點所對應的第一個邊結點 }VertexNode; typedef struct AdjList { int VexNum,ArcNum;//定義圖的頂點數和邊數 VertexNode vertex[MAX_VERTEX_NUM];//定義頭結點數組。 }AdjList; void CreateGraph(AdjList *adj,int *n) { int e,s,d; cout<<"輸入頂點數和邊數"<<endl; cin>>*n>>e;//輸入頂點數和邊數。 adj->VexNum=*n; adj->ArcNum=e; EdgeNode *q=NULL; //初始化表頭結點 int i; for(i=1;i<=*n;i++) { cout<<"輸入第"<<i<<"個結點的頂點名稱"<<endl; cin>>adj->vertex[i].data;//頂點名稱，是一個字符 adj->vertex[i].firstedge=NULL; } for(i=1;i<=e;i++) { cout<<"輸入第"<<i<<"條邊的起點和終點"<<endl; cin>>s>>d;//輸入邊的起始和終止 // cout<<"輸入表結點信息"<<endl; q=(EdgeNode *)malloc(sizeof(EdgeNode));//創建一個表結點 if(q==NULL) return; q->adjvex=d; // cin>>q->data; q->next=adj->vertex[s].firstedge;//新加入的節點都是在頭結點之后，原來在頭結點之后的節點要后移。 adj->vertex[s].firstedge=q; } } void DisplayGraph(AdjList *adj) { int n=adj->VexNum;//頂點個數，后面要遍歷每一個點點 EdgeNode *q=NULL; int i; for( i=1;i<=n;i++) { // cout<<n<<endl; q=adj->vertex[i].firstedge; if(q==NULL)//表示頭結點后面沒有跟其他結點 { cout<<"沒用從"<<adj->vertex[i].data<<"出發的節點"<<endl; } else { cout<<"從結點"<<adj->vertex[i].data<<"出發的邊有"<<endl; while(q!=NULL) { // cout<<adj->vertex[i].data<<"->"<<q->data<<endl; cout<<adj->vertex[i].data<<"->"<<adj->vertex[q->adjvex].data<<endl; q=q->next; } } } } void main() { int n; AdjList *adj=(AdjList *)malloc(sizeof(AdjList)); CreateGraph(adj,&n); DisplayGraph(adj); // cout<<"hello world!"<<endl; }?

輸出結果為：

輸入頂點數和邊數 6 6 輸入第1個結點的頂點名稱 a 輸入第2個結點的頂點名稱 b 輸入第3個結點的頂點名稱 c 輸入第4個結點的頂點名稱 d 輸入第5個結點的頂點名稱 e 輸入第6個結點的頂點名稱 f 輸入第1條邊的起點和終點 1 3 輸入第2條邊的起點和終點 2 4 輸入第3條邊的起點和終點 2 1 輸入第4條邊的起點和終點 4 3 輸入第5條邊的起點和終點 3 6 輸入第6條邊的起點和終點 3 5 從結點a出發的邊有 a->c 從結點b出發的邊有 b->a b->d 從結點c出發的邊有 c->e c->f 從結點d出發的邊有 d->c 沒用從e出發的節點 沒用從f出發的節點?

3.代碼實例2(ps:補充于2011-6-14)

? ? ? 總體而言，鄰接表表示法中主要含有兩種結點，分別是頭結點和表結點(也叫做邊結點)，在頭結點(s)到表結點(d)之間存在著一條邊。如果頭結點后面有多個表結點，即s->d1->d2，則表示存在著兩條邊，分別是e(s,d1)和e(s,d2)。鄰接表表示法中，頭結點的數量是固定的，就是圖中的頂點數量V，表結點的數量由邊的數量來決定。如果是有向圖，表結點的數量=邊的數量；如果是無向圖，則表結點的數量=邊的數量*2。

? ? ? 在構造圖的時候，如果一個頭結點后面有多個表結點，那么表結點按次序添加在頭結點后面。比如原先有結構s->d1->d2，現在需要添加表結點d3，那么需要打斷s->d1的指針，讓d3指向d1，s指向d3。即s->d3->d1->d2。

#include<iostream> #include<stdlib.h> using namespace std; #define MAX_VERTEX_NUM 50//定義圖的最大頂點數 typedef char VertexData;//頂點名稱是字符型。 typedef struct EdgeNode//表結點 { int adjvex;//鄰接點域 VertexData data; EdgeNode *next;//表結點所對應的下一個表結點 } EdgeNode; typedef struct VertexNode//頭結點 { VertexData data; EdgeNode *firstedge;//頭結點所對應的第一個表結點 }VertexNode; typedef struct AdjList//圖的數據結構 { int VexNum,ArcNum;//定義圖的頂點數和邊數 VertexNode vertex[MAX_VERTEX_NUM];//定義頭結點數組。 }AdjList; void CreateGraph(AdjList *adj) { int s,d; int i; cout<<"輸入頂點數和邊數"<<endl; cin>>adj->VexNum>>adj->ArcNum;//輸入圖的頂點數和邊數。 EdgeNode *q=NULL;//定義表結點 //初始化表頭結點 cout<<"輸入"<<adj->VexNum<<"個頭結點的名稱"<<endl; for(i=1;i<=adj->VexNum;i++) { //adj->vertex[i]是頭結點數組 cin>>adj->vertex[i].data;//頂點名稱，是一個字符 adj->vertex[i].firstedge=NULL;//初始狀態下頭結點后面不跟表結點，因此firstedge=null } //在初始化頭結點以后，就需要開始將表結點添加到頭結點后面去。 cout<<"輸入"<<adj->ArcNum<<"條邊的起點和終點"<<endl; for(i=1;i<=adj->ArcNum;i++) { cin>>s>>d;//輸入邊的起始和終止，起始s就是頭結點位置，終止d就是表結點位置 q=(EdgeNode *)malloc(sizeof(EdgeNode));//創建一個表結點，為其分配空間 if(q==NULL) return; /* 如果原來的鏈表是s->a->b-c>，現在要加入一個表結點q，那么加入以后就變成了s->q->a->b->c 因此： 1.q所指向的應該是當前s所指向的元素。 2.q的鄰接點域是d 3.s的指針指向q 操作如以下三行代碼 */ q->adjvex=d;//表結點的鄰接點域是d q->next=adj->vertex[s].firstedge;//新加入的節點都是在頭結點之后，原來在頭結點之后的節點要后移。 adj->vertex[s].firstedge=q; } } void DisplayGraph(AdjList *adj) { int n=adj->VexNum;//頂點個數，后面要遍歷每一個點點 EdgeNode *q=NULL; int i; for( i=1;i<=adj->VexNum;i++) { // cout<<n<<endl; q=adj->vertex[i].firstedge;//q為頭結點i所指向的表結點，i->q之間存在邊 if(q==NULL)//表示頭結點后面沒有跟其他結點 { cout<<"沒用從"<<adj->vertex[i].data<<"出發的節點"<<endl; } else { cout<<"從結點"<<adj->vertex[i].data<<"出發的邊有"<<endl; while(q!=NULL) { // cout<<adj->vertex[i].data<<"->"<<q->data<<endl; cout<<adj->vertex[i].data<<"->"<<adj->vertex[q->adjvex].data<<endl; q=q->next;//鏈表往后跳 } } } } void main() { int n; AdjList *adj=(AdjList *)malloc(sizeof(AdjList)); CreateGraph(adj); DisplayGraph(adj); system("pause"); } /* 輸入頂點數和邊數 6 6 輸入6個頭結點的名稱 a b c d e f 輸入6條邊的起點和終點 1 3 2 4 2 1 4 3 3 6 3 5 從結點a出發的邊有 a->c 從結點b出發的邊有 b->a b->d 從結點c出發的邊有 c->e c->f 從結點d出發的邊有 d->c 沒用從e出發的節點 沒用從f出發的節點 請按任意鍵繼續. . . */?

?

轉載于:https://www.cnblogs.com/xwdreamer/archive/2011/04/15/2297028.html

總結

以上是生活随笔為你收集整理的有向图的邻接表表示法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。