图的两种存储结构及四种形态——邻接矩阵、邻接表；有向图、无向图、有向网、无向网。
程序员文章站
2023-04-05 14:00:52
声明： 代码中有大量的注释，所以此处就不再作出大量的解释了。 一 ：邻接矩阵存储结构 1.首先是各种类型与宏的定义： 1 #include 2 using namespace std; 3 //无穷大 4 #define INFINITY INT_MAX 5 //最大顶点个数 ......
声明： 代码中有大量的注释，所以此处就不再作出大量的解释了。
一 ：邻接矩阵存储结构
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;
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;
}
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;
}
}
二 ：邻接表存储结构
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 }
上一篇： python的exe反编译