圖的兩種存儲結構及四種形态——鄰接矩陣、鄰接表；有向圖、無向圖、有向網、無向網。
Posted on 2019-08-04 17:12 水龍頭 閱讀(...) 評論(...) 編輯 收藏
聲明： 代碼中有大量的注釋，是以此處就不再作出大量的解釋了。
一 ：鄰接矩陣存儲結構
1.首先是各種類型與宏的定義：
1 #include <iostream>
2 using namespace std;
3 //無窮大
4 #define INFINITY INT_MAX
5 //最大頂點個數
6 #define MAX_VERTEX_NUM 20
7 //頂點類型
8 typedef char VertexType;
9 typedef int VRType;
10 typedef char infoType;
11 //圖的四種類型
12 typedef enum {DG = 1, DN, UDG, UDN} GraphKind;
13
14 //弧的結構體定義
15 typedef struct ArcCell
16 {
17 // 對于網來說是權值；對于圖來說就是0或1
18 VRType adj;
19 //該弧相關資訊的指針（現在暫且可以了解為字元指針）
20 infoType* info;
21 }ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
22
23 //圖的結構體定義
24 typedef struct
25 {
26 VertexType vexs[MAX_VERTEX_NUM];
27 //arcs可以先簡單地了解為一個數組名
28 AdjMatrix arcs;
29 //目前圖中的頂點數和弧數
30 int vexnum, arcnum;
31 //圖的種類标志
32 GraphKind kind;
33 }MGraph; View Code
2.接下來是函數聲明及main函數：
void CreateGraph(MGraph &G);
void CreateUDN(MGraph &G);
int LocateVex(MGraph G , int v1);
void CreateUDG(MGraph &G);
void CreateDG(MGraph &G);
void CreateDN(MGraph &G);
void Print(MGraph G);
int main(void)
{
MGraph G;
CreateGraph(G);
return 0;
} View Code
3.最後就是各種自定義函數的定義了：
void CreateGraph(MGraph &G)
{
cout << "1、有向圖" << endl;
cout << "2、有向網" << endl;
cout << "3、無向圖" << endl;
cout << "4、無向網" << endl;
cout << "你需要建立哪一種類型的圖?" << endl;
//此處運用了強轉（不能直接從鍵盤上給枚舉變量指派）
cin >> (int&)G.kind;
switch (G.kind)
{
case 1:
return CreateDG(G);
break;
case 2:
return CreateDN(G);
break;
case 3:
return CreateUDG(G);
break;
case 4:
return CreateUDN(G);
break;
}
}
//建立有向網
void CreateDN(MGraph &G)
{
cout << "該圖有多少頂點以及多少條弧?" << endl;
cin >> G.vexnum >> G.arcnum;
cout << "請輸入頂點:" << endl;
for(int i = 0; i < G.vexnum; i++)
{
//cin相當于c裡面的scanf函數
cin >> G.vexs[i];
}
for(int i = 0; i < G.vexnum; i++)
{
for(int j = 0; j < G.vexnum; j++)
{
//先假設每兩個點之間都沒有邊
G.arcs[i][j].adj = INFINITY;
}
}
cout << "請輸入各弧的兩個端點及其權值" << endl;
VertexType v1, v2;
//用于暫時存儲每條弧的權值
VRType temp;
int i, j;
//有向網不具備對稱性
for(int k = 0; k < G.arcnum; k++)
{
cin >> v1 >> v2 >> temp;
//利用存儲頂點所用的一維數組中對應點的下标
i = LocateVex(G, v1), j = LocateVex(G, v2),
G.arcs[i][j].adj = temp;
}
Print(G);
}
//建立有向圖
void CreateDG(MGraph &G)
{
cout << "該圖有多少頂點以及多少條邊?" << endl;
cin >> G.vexnum >> G.arcnum;
cout << "請輸入頂點:" << endl;
for(int i = 0; i < G.vexnum; i++)
{
cin >> G.vexs[i];
}
for(int i = 0; i < G.vexnum; i++)
{
for(int j = 0; j < G.vexnum; j++)
{
//先假定圖中沒有弧
G.arcs[i][j].adj = 0;
}
}
cout << "請輸入各弧的兩個端點" << endl;
VertexType v1, v2;
//用于暫時存儲每條弧的'權值'(存在即為1,否則為0)
//因為temp的取值隻能為1或0，是以不需要再輸入
VRType temp = 1;
int i, j;
//有向圖不具備對稱性
for(int k = 0; k < G.arcnum; k++)
{
cin >> v1 >> v2;
i = LocateVex(G, v1), j = LocateVex(G, v2),
G.arcs[i][j].adj = temp;
}
Print(G);
}
//建立無向圖（對稱）
void CreateUDG(MGraph &G)
{
cout << "該圖有多少頂點以及多少條邊?" << endl;
cin >> G.vexnum >> G.arcnum;
cout << "請輸入頂點:" << endl;
for(int i = 0; i < G.vexnum; i++)
{
cin >> G.vexs[i];
}
for(int i = 0; i < G.vexnum; i++)
{
for(int j = 0; j < G.vexnum; j++)
{
//先假設每兩個點之間都沒有邊
G.arcs[i][j].adj = 0;
}
}
cout << "請輸入各弧的兩個端點(下三角)" << endl;
VertexType v1, v2;
VRType temp = 1;
int i, j;
//考慮到無向圖具有對稱性（先隻輸入(鄰接矩陣)下三角裡存在的邊）
for(int k = 0; k < G.arcnum; k++)
{
cin >> v1 >> v2;
i = LocateVex(G, v1), j = LocateVex(G, v2),
G.arcs[i][j].adj = temp;
//将上三角裡的每條弧同樣添加上權值
G.arcs[j][i].adj = G.arcs[i][j].adj;
}
Print(G);
}
//建立無向網（對稱）
void CreateUDN(MGraph &G)
{
cout << "該圖有多少頂點以及多少條邊?" << endl;
cin >> G.vexnum >> G.arcnum;
cout << "請輸入頂點:" << endl;
for(int i = 0; i < G.vexnum; i++)
{
cin >> G.vexs[i];
}
for(int i = 0; i < G.vexnum; i++)
{
for(int j = 0; j < G.vexnum; j++)
{
//先假設每兩個點之間都沒有邊(無窮遠)
G.arcs[i][j].adj = INFINITY;
}
}
cout << "請輸入各弧的兩個端點及其權值(下三角)" << endl;
VertexType v1, v2;
VRType temp;
int i, j;
//考慮到無向圖具有對稱性（先隻輸入(鄰接矩陣)下三角裡存在的邊）
for(int k = 0; k < G.arcnum; k++)
{
cin >> v1 >> v2 >> temp;
i = LocateVex(G, v1), j = LocateVex(G, v2),
G.arcs[i][j].adj = temp;
//将上三角裡的每條弧同樣添加上權值
G.arcs[j][i].adj = G.arcs[i][j].adj;
}
Print(G);
}
//傳回該頂點在一維數組中的下标（當然每一個人建立的一維數組可以是不同的）
int LocateVex(MGraph G , int v1)
{
for(int i = 0; i < G.vexnum; i++)
{
if(G.vexs[i] == v1)
return i;
}
}
void Print(MGraph G)
{
cout << "存儲的一維數組如下:" << endl;
for(int i = 0; i < G.vexnum; i++)
{
cout << G.vexs[i] << '\t';
}
cout << endl;
cout << "鄰接矩陣如下:" << endl;
for(int i = 0; i < G.vexnum; i++)
{
for(int j = 0; j < G.vexnum; j++)
{
cout << G.arcs[i][j].adj << '\t';
}
cout << endl;
}
} View Code
二 ：鄰接表存儲結構
1 #include <iostream>
2 #include <string>
3 using namespace std;
4 using std :: string;
5 typedef string InforType;
6 //頂點類型
7 typedef char VertexType;
8 typedef int Status;
9 typedef enum {UDG = 1, DG, UDN, DN} GraphKind;
10 //最大頂點個數
11 #define MAX_VERTEX_NUM 20
12 #define ERROR -1
13 #define OK 1
14 //表節點的定義
15 typedef struct ArcNode
16 {
17 //該弧所指向的頂點的位置（相對位址）
18 int adjvex;
19 //指向下一條弧的指針
20 struct ArcNode* nextarc;
21 //該弧相關資訊的指針（例如權值）
22 InforType info;
23 }ArcNode;
24 //頭節點的定義
25 typedef struct VNode
26 {
27 //頂點資訊
28 VertexType data;
29 //指向第一條依附該頂點的弧的指針
30 ArcNode* firstarc;
31 }VNode, AdjList[MAX_VERTEX_NUM];
32 //圖的定義
33 typedef struct
34 {
35 //存放頭節點的一維數組
36 AdjList vertices;
37 //圖的目前頂點數和弧數
38 int vexnum, arcnum;
39 //圖的種類标志
40 GraphKind kind;
41 }ALGraph;
42 void CreateGraph(ALGraph& G);
43 Status CreateUDN(ALGraph& G);
44 Status CreateUDG(ALGraph& G);
45 Status CreateDG(ALGraph& G);
46 Status CreateDN(ALGraph& G);
47 int LocateVex(VNode vertices[], int vexnum, VertexType e);
48 void Print(const ALGraph& G);
49 int main(void)
50 {
51 ALGraph G;
52 CreateGraph(G);
53 return 0;
54 }
55 void CreateGraph(ALGraph& G)
56 {
57 int reply;
58 cout << "1. 無向圖" << endl;
59 cout << "2. 有向圖" << endl;
60 cout << "3. 無向網" << endl;
61 cout << "4. 有向網" << endl;
62 //其實逆與正是差不多的，根本上還是取決于使用者的輸入
63 cout << "5. 逆有向網" << endl;
64 cout << "6. 逆有向圖" << endl;
65 cout << "你想建立哪一種類型的圖?" << endl;
66 cin >> reply;
67 switch(reply)
68 {
69 case 1:
70 CreateUDG(G);
71 break;
72 case 2:
73 CreateDG(G);
74 break;
75 case 3:
76 CreateUDN(G);
77 break;
78 case 4:
79 CreateDN(G);
80 break;
81 case 5:
82 CreateDN(G);
83 break;
84 case 6:
85 CreateDG(G);
86 break;
87 default:
88 exit(-1);
89 }
90 }
91 //構造無向網
92 Status CreateUDN(ALGraph& G)
93 {
94 VertexType e;
95 int num;
96 cout << "該圖共有多少個頂點、多少條弧?" << endl;
97 cin >> G.vexnum >> G.arcnum;
98 cout << "請輸入各頂點:" << endl;
99 for(int i = 0; i < G.vexnum; i++)
100 {
101 //注意存儲結構
102 cin >> G.vertices[i].data;
103 //先将頭節點的指針域設為空
104 G.vertices[i].firstarc = NULL;
105 }
106 for(int i = 0; i < G.vexnum; i++)
107 {
108 //(強調引用)
109 //注意ptr是節點的指針（是節點類型的一部分）而不是‘指向’節點的指針
110 //是以接連各節點不想以前那樣簡單了
111 ArcNode* &ptr = G.vertices[i].firstarc;
112 cout << "請問以頂點" << G.vertices[i].data << "為起點的弧一共有多少條?" << endl;
113 cin >> num;
114 if(num > 0)
115 {
116 int Index;
117 ArcNode* p = NULL;
118 cout << "請将這些頂點及弧所帶資訊依次輸入:" << endl;
119 //先處理一個節點（為了友善後面的操作）
120 ptr = new ArcNode;
121 if(ptr)
122 {
123 cin >> e;
124 //輸入弧上的資訊
125 cin >> ptr->info;
126 Index = LocateVex(G.vertices, G.vexnum, e);
127 p = ptr;
128 p->adjvex = Index;
129 p->nextarc = NULL;
130 }
131 else
132 return ERROR;
133 for(int j = 1; j < num; j++)
134 {
135 ArcNode* ptr2 = new ArcNode;
136 if(ptr2)
137 {
138 //注意各變量的類型，不要搞混了
139 cin >> e;
140 //輸入弧上的資訊
141 cin >> ptr2->info;
142 Index = LocateVex(G.vertices, G.vexnum, e);
143 ptr2->adjvex = Index;
144 ptr2->nextarc = NULL;
145 //注意此處的連接配接節點與以前寫的有點不同（ptr‘一直’為空）
146 p->nextarc = ptr2;
147 p = p->nextarc;
148 }
149 else
150 return ERROR;
151 }
152 }
153 }
154 Print(G);
155 return OK;
156 }
157 //構造無向圖
158 Status CreateUDG(ALGraph& G)
159 {
160 VertexType e;
161 int num;
162 cout << "該圖共有多少個頂點、多少條弧?" << endl;
163 cin >> G.vexnum >> G.arcnum;
164 cout << "請輸入各頂點:" << endl;
165 for(int i = 0; i < G.vexnum; i++)
166 {
167 //注意存儲結構
168 cin >> G.vertices[i].data;
169 //先将頭節點的指針域設為空
170 G.vertices[i].firstarc = NULL;
171 }
172 for(int i = 0; i < G.vexnum; i++)
173 {
174 //(強調引用)
175 //注意ptr是節點的指針（是節點類型的一部分）而不是‘指向’節點的指針
176 //是以接連各節點不想以前那樣簡單了
177 ArcNode* &ptr = G.vertices[i].firstarc;
178 cout << "請問以頂點" << G.vertices[i].data << "為起點的弧一共有多少條?" << endl;
179 cin >> num;
180 if(num > 0)
181 {
182 int Index;
183 ArcNode* p = NULL;
184 cout << "請将這些頂點依次輸入:" << endl;
185 //先處理一個節點（為了友善後面的操作）
186 ptr = new ArcNode;
187 if(ptr)
188 {
189 cin >> e;
190 Index = LocateVex(G.vertices, G.vexnum, e);
191 p = ptr;
192 p->adjvex = Index;
193 p->nextarc = NULL;
194 }
195 else
196 return ERROR;
197 for(int j = 1; j < num; j++)
198 {
199 //注意各變量的類型，不要搞混了
200 cin >> e;
201 Index = LocateVex(G.vertices, G.vexnum, e);
202 ArcNode* ptr2 = new ArcNode;
203 if(ptr2)
204 {
205 ptr2->adjvex = Index;
206 ptr2->nextarc = NULL;
207 //注意此處的連接配接節點與以前寫的有點不同（ptr‘一直’為空）
208 p->nextarc = ptr2;
209 p = p->nextarc;
210 }
211 else
212 return ERROR;
213 }
214 }
215 }
216 Print(G);
217 return OK;
218 }
219 //構造有向圖
220 Status CreateDG(ALGraph& G)
221 {
222 VertexType e;
223 int num;
224 cout << "該圖共有多少個頂點、多少條弧?" << endl;
225 cin >> G.vexnum >> G.arcnum;
226 cout << "請輸入各頂點:" << endl;
227 for(int i = 0; i < G.vexnum; i++)
228 {
229 //注意存儲結構
230 cin >> G.vertices[i].data;
231 //先将頭節點的指針域設為空
232 G.vertices[i].firstarc = NULL;
233 }
234 for(int i = 0; i < G.vexnum; i++)
235 {
236 //(強調引用)
237 //注意ptr是節點的指針（是節點類型的一部分）而不是‘指向’節點的指針
238 //是以接連各節點不想以前那樣簡單了
239 ArcNode* &ptr = G.vertices[i].firstarc;
240 cout << "請問以頂點" << G.vertices[i].data << "為起點的弧一共有多少條?" << endl;
241 cin >> num;
242 if(num > 0)
243 {
244 int Index;
245 ArcNode* p = NULL;
246 cout << "請将這些頂點依次輸入:" << endl;
247 //先處理一個節點（為了友善後面的操作）
248 ptr = new ArcNode;
249 if(ptr)
250 {
251 cin >> e;
252 Index = LocateVex(G.vertices, G.vexnum, e);
253 p = ptr;
254 p->adjvex = Index;
255 p->nextarc = NULL;
256 }
257 else
258 return ERROR;
259 for(int j = 1; j < num; j++)
260 {
261 //注意各變量的類型，不要搞混了
262 cin >> e;
263 Index = LocateVex(G.vertices, G.vexnum, e);
264 ArcNode* ptr2 = new ArcNode;
265 if(ptr2)
266 {
267 ptr2->adjvex = Index;
268 ptr2->nextarc = NULL;
269 //注意此處的連接配接節點與以前寫的有點不同（ptr‘一直’為空）
270 p->nextarc = ptr2;
271 p = p->nextarc;
272 }
273 else
274 return ERROR;
275 }
276 }
277 }
278 Print(G);
279 return OK;
280 }
281 //構造有向網
282 Status CreateDN(ALGraph& G)
283 {
284 VertexType e;
285 int num;
286 cout << "該圖共有多少個頂點、多少條弧?" << endl;
287 cin >> G.vexnum >> G.arcnum;
288 cout << "請輸入各頂點:" << endl;
289 for(int i = 0; i < G.vexnum; i++)
290 {
291 //注意存儲結構
292 cin >> G.vertices[i].data;
293 //先将頭節點的指針域設為空
294 G.vertices[i].firstarc = NULL;
295 }
296 for(int i = 0; i < G.vexnum; i++)
297 {
298 //(強調引用)
299 //注意ptr是節點的指針（是節點類型的一部分）而不是‘指向’節點的指針
300 //是以接連各節點不想以前那樣簡單了
301 ArcNode* &ptr = G.vertices[i].firstarc;
302 cout << "請問以頂點" << G.vertices[i].data << "為起點的弧一共有多少條?" << endl;
303 cin >> num;
304 if(num > 0)
305 {
306 int Index;
307 ArcNode* p = NULL;
308 cout << "請将這些頂點及弧所帶資訊依次輸入:" << endl;
309 //先處理一個節點（為了友善後面的操作）
310 ptr = new ArcNode;
311 if(ptr)
312 {
313 cin >> e;
314 //輸入弧上的資訊
315 cin >> ptr->info;
316 Index = LocateVex(G.vertices, G.vexnum, e);
317 p = ptr;
318 p->adjvex = Index;
319 p->nextarc = NULL;
320 }
321 else
322 return ERROR;
323 for(int j = 1; j < num; j++)
324 {
325 ArcNode* ptr2 = new ArcNode;
326 if(ptr2)
327 {
328 //注意各變量的類型，不要搞混了
329 cin >> e;
330 //輸入弧上的資訊
331 cin >> ptr2->info;
332 Index = LocateVex(G.vertices, G.vexnum, e);
333 ptr2->adjvex = Index;
334 ptr2->nextarc = NULL;
335 //注意此處的連接配接節點與以前寫的有點不同（ptr‘一直’為空）
336 p->nextarc = ptr2;
337 p = p->nextarc;
338 }
339 else
340 return ERROR;
341 }
342 }
343 }
344 Print(G);
345 return OK;
346 }
347 //定位頂點在一維數組中的位置
348 int LocateVex(VNode vertices[], int vexnum, VertexType e)
349 {
350 int i;
351 for(i = 0; i < vexnum; i++)
352 {
353 if(vertices[i].data == e)
354 break;
355 }
356 return i;
357 }
358 //列印圖
359 void Print(const ALGraph& G)
360 {
361 cout << "您所建立的圖用鄰接表存儲結構展示如下:" << endl;
362 for(int i = 0; i < G.vexnum; i++)
363 {
364 cout << "[" << G.vertices[i].data << "]";
365 ArcNode* ptr = G.vertices[i].firstarc;
366 while(ptr)
367 {
368 //列印出下标（從零開始）
369 cout << "—>" << ptr->adjvex;
370 ptr = ptr->nextarc;
371 }
372 cout << endl;
373 }
374 } View Code