图的两种存储结构及四种形态——邻接矩阵、邻接表；有向图、无向图、有向网、无向网。
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