? ? ? ?鄰接多重表(Adjacency Multilist)主要用于存儲無向圖。因為，如果用鄰接表存儲無向圖，每條邊的兩個邊結點分別在以該邊

所依附的兩個頂點為頭結點的鏈表中，這給圖的某些操作帶來不便。例如，對已訪問過的邊做標記，或者要刪除圖中某一條邊等，

都需要找到表示同一條邊的兩個結點。因此，在進行這一類操作的無向圖的問題中采用鄰接多重表作存儲結構更為適宜。

?

? ? ? ?鄰接多重表的存儲結構和十字鏈表類似，也是由頂點表和邊表組成，每一條邊用一個結點表示，其頂點表結點結構和邊表結點

結構如圖8.15 所示。

其中，頂點表由兩個域組成，vertex 域存儲和該頂點相關的信息firstedge 域指示第一條依附于該頂點的邊；邊表結點由六個域

組成，mark 為標記域，可用以標記該條邊是否被搜索過；ivex 和jvex 為該邊依附的兩個頂點在圖中的位置；ilink 指向下一條依

附于頂點ivex的邊;jlink 指向下一條依附于頂點jvex 的邊，info 為指向和邊相關的各種信息的指針域。

例如，圖8.16 所示為無向圖8.1 的鄰接多重表。在鄰接多重表中，所有依附于同一頂點的邊串聯在同一鏈表中，由于每條邊依附于兩個頂

點，則每個邊結點同時鏈接在兩個鏈表中。可見，對無向圖而言，其鄰接多重表和鄰接表的差別，僅僅在于同一條邊在鄰接表中用兩個結

點表示，而在鄰接多重表中只有一個結點。因此，除了在邊結點中增加一個標志域外，鄰接多重表所需的存儲量和鄰接表相同。在鄰接多

重表上，各種基本操作的實現亦和鄰接表相似。

代碼如下:

1 #include "stdafx.h" 2 #include<iostream> 3 using namespace std; 4 5 typedef int VertexType; 6 #define MAX_VERTEX_NUM 20 7 typedef enum{unvisited,visited} VisitIf; 8 typedef struct EBox 9 { 10 VisitIf mark; //訪問標記 11 int ivex, jvex; //該邊依附的兩個頂點的位置 12 struct EBox *ilink, *jlink;//分別指向依附的兩個頂點的下一條邊 13 int info; //該邊信息指針，可指向權值或其他信息 14 }EBox; 15 typedef struct VexBox 16 { 17 VertexType data; 18 EBox *firstarc; //指向第一條依附改點的邊 19 }VexBox; 20 typedef struct 21 { 22 VexBox adjmulist[MAX_VERTEX_NUM]; 23 int vexnum, arcnum; //無向圖的當前頂點數和邊數 24 }AMLGraph; 25 26 int LocateVex(AMLGraph G, VertexType v)// 初始條件：無向圖G存在，v和G中頂點有相同特征 27 // 操作結果：若G中存在頂點v，則返回該頂點在無向圖中位置；否則返回-1 28 { 29 for (int i = 0; i < G.vexnum; i++) 30 if (G.adjmulist[i].data == v) 31 return i; 32 return -1; 33 } 34 35 void CreateGraph(AMLGraph &G)//采用鄰接多重表構建無向圖G 36 { 37 VertexType v1, v2; 38 cout << "請輸入總頂點數和總邊數(用空格隔開):"; 39 cin >> G.vexnum >> G.arcnum; 40 cout << "輸入頂點" << endl; 41 for (int i = 0; i < G.vexnum; i++)//構造頂點向量 42 { 43 cin >> G.adjmulist[i].data ; 44 G.adjmulist[i].firstarc = NULL; 45 } 46 cout << "請輸入每條邊的兩個端點以及權值:" << endl; 47 for (int k = 0; k < G.arcnum; k++)//構造表結點鏈表 48 { 49 EBox *p = new EBox;; 50 cin >> v1 >> v2 >>p->info; 51 int m = LocateVex(G, v1);//一端 52 int n = LocateVex(G, v2);//另一端 53 p->mark = unvisited; 54 p->ivex = m; //插在一端表頭 55 p->ilink = G.adjmulist[m].firstarc; 56 G.adjmulist[m].firstarc = p; 57 p->jvex = n; //插在另一端表頭 58 p->jlink = G.adjmulist[n].firstarc; 59 G.adjmulist[n].firstarc = p; 60 } 61 } 62 63 void MarkUnvizited(AMLGraph G)//置邊的訪問標記為未被訪問 64 { 65 int i; 66 EBox *p; 67 for (i = 0; i<G.vexnum; i++) 68 { 69 p = G.adjmulist[i].firstarc; 70 while (p) 71 { 72 p->mark = unvisited; 73 if (p->ivex == i) 74 p = p->ilink; 75 else 76 p = p->jlink; 77 } 78 } 79 } 80 81 82 void display(AMLGraph G)//輸出無向圖的鄰接多重表 83 { 84 EBox *p; 85 MarkUnvizited(G); 86 cout << "無向圖有" << G.vexnum << "個頂點，分別為:"; 87 for (int i = 0; i < G.vexnum; i++) 88 { 89 cout << G.adjmulist[i].data << " "; 90 91 } 92 cout << endl; 93 for (int i = 0; i < G.vexnum; i++) 94 { 95 cout << "和" << G.adjmulist[i].data << "有關的邊:"; 96 p = G.adjmulist[i].firstarc; 97 while (p) 98 { 99 if (p->ivex == i) // 邊的m端與該頂點有關 100 { 101 if (p->mark) 102 { 103 cout << G.adjmulist[i].data <<" "<< G.adjmulist[p->jvex].data<<" "; 104 p->mark = visited; 105 if (p->info) 106 cout << "權值:" << p->info << ". "; 107 } 108 p = p->ilink; 109 } 110 else // 邊的n端與該頂點有關 111 { 112 if (!p->mark) 113 { 114 cout << G.adjmulist[p->ivex].data <<" "<< G.adjmulist[i].data<<" "; 115 p->mark = visited; 116 if (p->info) 117 cout << "權值:" << p->info << ". "; 118 } 119 p = p->jlink; 120 } 121 } 122 cout << endl; 123 } 124 } 125 126 int main() 127 { 128 AMLGraph MG; 129 CreateGraph(MG); 130 display(MG); 131 return 0; 132 }

?

輸出結果：

轉載于:https://www.cnblogs.com/Trojan00/p/8964609.html

總結

以上是生活随笔為你收集整理的数据结构之图(2-2)【邻接多重表】适用于无向图的全部內容，希望文章能夠幫你解決所遇到的問題。

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