《数据布局（C语言版）第二版》第六章-图（6.4 图的存储布局——6.4.2 毗邻 ...

6.4.2 毗邻表

接纳毗邻表表现法创建无向图

1. //算法6.2 采用邻接表表示法创建无向图
3. #include <stdio.h>
4. #include <stdlib.h>
6. #define MVNum 100
8. typedef int OtherInfo;   //假设在边结点中的数据域存储边的权值,且边的权值类型为整型
9. typedef char VerTexType;  //假设顶点的数据类型为字符型
11. typedef struct ArcNode
12. {
13.         int adjvex;
14.         struct ArcNode* nextarc;
15.         OtherInfo info;
16. }ArcNode;  //边结点
18. typedef struct VNode
19. {
20.         VerTexType data;
21.         ArcNode* firstarc;
22. }VNode,AdjList[MVNum];  //表头结点
24. typedef struct
25. {
26.         AdjList vertices;  //存储所有顶点
27.         int vexnum;  //顶点总数
28.         int arcnum;  //总边数
29. }ALGraph;  //图的信息
31. void CreateUDG(ALGraph& G);
32. int LocateVex(ALGraph& G, VerTexType v);
33. void printALGraph(ALGraph &G);
35. int main()
36. {
37.         ALGraph G = { {'\0',NULL}, 0,0};
38.         CreateUDG(G);
39.         printALGraph(G);
41.         return 0;
42. }
44. void CreateUDG(ALGraph& G)
45. {
46.         int i = 0;
47.         int k = 0;
48.         VerTexType v1 = 0;
49.         VerTexType v2 = 0;
50.         int j = 0;
51.         ArcNode *p1 = NULL;
52.         ArcNode *p2 = NULL;
54.         printf("请输入无向图的总顶点数：");
55.         scanf_s(" %d", &G.vexnum);
57.         printf("请输入无向图的总边数：");
58.         scanf_s(" %d", &G.arcnum);
60.         for (i = 0; i < G.vexnum; ++i)
61.         {
62.                 printf("请输入第%d个顶点的值：", i + 1);
63.                 scanf_s(" %c", &(G.vertices[i].data));
64.                 G.vertices[i].firstarc = NULL;   //初始化
65.         }
67.         for (k = 0; k < G.arcnum; k++)
68.         {
69.                 printf("请输入第%d条边依附的两个顶点（用空格间隔，输入结束后按回车）: ", k + 1);
70.                 scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));
72.                 i = LocateVex(G, v1);
73.                 j = LocateVex(G, v2);
75.                 p1 = (ArcNode*)malloc(sizeof(ArcNode));
76.                 p1->adjvex = j;
77.                 p1->nextarc = G.vertices[i].firstarc;
78.                 G.vertices[i].firstarc = p1;  //将新结点*p1插入顶点Vi的边表头部
80.                 p2 = (ArcNode*)malloc(sizeof(ArcNode));
81.                 p2->adjvex = i;
82.                 p2->nextarc = G.vertices[j].firstarc;
83.                 G.vertices[j].firstarc = p2;  //将与*p1对称的新的边结点*p2插入顶点Vj的边表头部
84.         }
85. }
88. //在G的顶点表vexs中获取字符v的下标（数组G.vexs的下标从0开始）
89. int LocateVex(ALGraph& G, VerTexType v)
90. {
91.         int i = 0;
92.         for (i = 0; i < G.vexnum && (G.vertices[i].data != v); ++i)
93.         {
94.                 ;
95.         }
97.         return i;
98. }
101. //打印邻接表
102. void printALGraph(ALGraph& G)
103. {
104.         int i = 0;
105.         ArcNode* pMove = NULL;
107.         for (i = 0; i < G.vexnum; i++)
108.         {
109.                 printf("\n第%d个顶点为：%c", i + 1, G.vertices[i].data);
111.                 pMove = G.vertices[i].firstarc;
112.                 if (pMove)
113.                 {
114.                         printf("\n与第%d个顶点相邻接的每个顶点在图中的位置（下标值）为：", i + 1);
115.                         while (pMove)
116.                         {
117.                                 printf("%d ", pMove->adjvex);
118.                                 pMove = pMove->nextarc;
119.                         }
120.                 }
121.                 else
122.                 {
123.                         printf("\n没有与第%d个顶点相邻接的顶点。", i + 1);
124.                 }
125.         }
126. }

复制代码

   一个图的毗邻矩阵表现是唯一的，但其毗邻表表现不唯一。
    不改变图中每个顶点的命名方式，也不改变图的边（每条边的起尽头），
仅改变边的输入序次时，图的毗邻表中每个顶点背面边表中的结点排序方式会发生变化。
由于图中的顶点没变，边也没变，每个顶点及其边表中的内容不会发生变化。
  

接纳毗邻表表现法创建有向图

1. //采用邻接表表示法创建有向图
3. #include <stdio.h>
4. #include <stdlib.h>
6. #define MVNum 100
8. typedef int OtherInfo;   //假设在边结点中的数据域存储边的权值,且边的权值类型为整型
9. typedef char VerTexType;  //假设顶点的数据类型为字符型
11. typedef struct ArcNode
12. {
13.         int adjvex;
14.         struct ArcNode* nextarc;
15.         OtherInfo info;
16. }ArcNode;  //边结点
18. typedef struct VNode
19. {
20.         VerTexType data;
21.         ArcNode* firstarc;
22. }VNode, AdjList[MVNum];  //表头结点
24. typedef struct
25. {
26.         AdjList vertices;  //存储所有顶点
27.         int vexnum;  //顶点总数
28.         int arcnum;  //总边数
29. }ALGraph;  //图的信息
31. void CreateDG(ALGraph& G);
32. int LocateVex(ALGraph& G, VerTexType v);
33. void printALGraph(ALGraph& G);
35. int main()
36. {
37.         ALGraph G = { {'\0',NULL}, 0,0 };
38.         CreateDG(G);
39.         printALGraph(G);
41.         return 0;
42. }
44. //采用邻接表表示法创建有向图
45. void CreateDG(ALGraph& G)
46. {
47.         int i = 0;
48.         int k = 0;
49.         VerTexType v1 = 0;
50.         VerTexType v2 = 0;
51.         int j = 0;
52.         ArcNode* p1 = NULL;
53.         ArcNode* p2 = NULL;
55.         printf("请输入有向图的总顶点数：");
56.         scanf_s(" %d", &G.vexnum);
58.         printf("请输入有向图的总边数：");
59.         scanf_s(" %d", &G.arcnum);
61.         for (i = 0; i < G.vexnum; ++i)
62.         {
63.                 printf("请输入第%d个顶点的值：", i + 1);
64.                 scanf_s(" %c", &(G.vertices[i].data));
65.                 G.vertices[i].firstarc = NULL;   //初始化
66.         }
68.         for (k = 0; k < G.arcnum; k++)
69.         {
70.                 printf("请输入第%d条边依附的两个顶点（用空格间隔，输入结束后按回车）: ", k + 1);
71.                 scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));
73.                 i = LocateVex(G, v1);
74.                 j = LocateVex(G, v2);
76.                 p1 = (ArcNode*)malloc(sizeof(ArcNode));
77.                 p1->adjvex = j;
78.                 p1->nextarc = G.vertices[i].firstarc;
79.                 G.vertices[i].firstarc = p1;  //将新结点*p1插入顶点Vi的边表头部
80.         }
81. }
84. //在G的顶点表vexs中获取字符v的下标（数组G.vexs的下标从0开始）
85. int LocateVex(ALGraph& G, VerTexType v)
86. {
87.         int i = 0;
88.         for (i = 0; i < G.vexnum && (G.vertices[i].data != v); ++i)
89.         {
90.                 ;
91.         }
93.         return i;
94. }
97. //打印邻接表
98. void printALGraph(ALGraph& G)
99. {
100.         int i = 0;
101.         ArcNode* pMove = NULL;
103.         for (i = 0; i < G.vexnum; i++)
104.         {
105.                 printf("\n第%d个顶点为：%c", i + 1, G.vertices[i].data);
107.                 pMove = G.vertices[i].firstarc;
108.                 if (pMove)
109.                 {
110.                         printf("\n将第%d个顶点作为出度，与其相邻接的每个顶点在图中的位置（下标值）为：", i + 1);
111.                         while (pMove)
112.                         {
113.                                 printf("%d ", pMove->adjvex);
114.                                 pMove = pMove->nextarc;
115.                         }
116.                 }
117.                 else
118.                 {
119.                         printf("\n将第%d个顶点作为出度，没有与其相邻接的顶点。", i + 1);
120.                 }
121.         }
122. }

复制代码

创建有向图的逆毗邻表

1. //创建有向图的逆邻接表
3. #include <stdio.h>
4. #include <stdlib.h>
6. #define MVNum 100
8. typedef int OtherInfo;   //假设在边结点中的数据域存储边的权值,且边的权值类型为整型
9. typedef char VerTexType;  //假设顶点的数据类型为字符型
11. typedef struct ArcNode
12. {
13.         int adjvex;
14.         struct ArcNode* nextarc;
15.         OtherInfo info;
16. }ArcNode;  //边结点
18. typedef struct VNode
19. {
20.         VerTexType data;
21.         ArcNode* firstarc;
22. }VNode, AdjList[MVNum];  //表头结点
24. typedef struct
25. {
26.         AdjList vertices;  //存储所有顶点
27.         int vexnum;  //顶点总数
28.         int arcnum;  //总边数
29. }ALGraph;  //图的信息
31. void CreateDG(ALGraph& G);
32. int LocateVex(ALGraph& G, VerTexType v);
33. void printALGraph(ALGraph& G);
35. int main()
36. {
37.         ALGraph G = { {'\0',NULL}, 0,0 };
38.         CreateDG(G);
39.         printALGraph(G);
41.         return 0;
42. }
44. //创建有向图的逆邻接表
45. void CreateDG(ALGraph& G)
46. {
47.         int i = 0;
48.         int k = 0;
49.         VerTexType v1 = 0;
50.         VerTexType v2 = 0;
51.         int j = 0;
52.         ArcNode* p1 = NULL;
53.         ArcNode* p2 = NULL;
55.         printf("请输入有向图的总顶点数：");
56.         scanf_s(" %d", &G.vexnum);
58.         printf("请输入有向图的总边数：");
59.         scanf_s(" %d", &G.arcnum);
61.         for (i = 0; i < G.vexnum; ++i)
62.         {
63.                 printf("请输入第%d个顶点的值：", i + 1);
64.                 scanf_s(" %c", &(G.vertices[i].data));
65.                 G.vertices[i].firstarc = NULL;   //初始化
66.         }
68.         for (k = 0; k < G.arcnum; k++)
69.         {
70.                 printf("请输入第%d条边依附的两个顶点（用空格间隔，输入结束后按回车）: ", k + 1);
71.                 scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));
73.                 i = LocateVex(G, v1);
74.                 j = LocateVex(G, v2);
76.                 p1 = (ArcNode*)malloc(sizeof(ArcNode));
77.                 p1->adjvex = i;
78.                 p1->nextarc = G.vertices[j].firstarc;
79.                 G.vertices[j].firstarc = p1;  //将新结点*p1插入顶点Vj的边表头部
80.         }
81. }
84. //在G的顶点表vexs中获取字符v的下标（数组G.vexs的下标从0开始）
85. int LocateVex(ALGraph& G, VerTexType v)
86. {
87.         int i = 0;
88.         for (i = 0; i < G.vexnum && (G.vertices[i].data != v); ++i)
89.         {
90.                 ;
91.         }
93.         return i;
94. }
97. //打印逆邻接表
98. void printALGraph(ALGraph& G)
99. {
100.         int i = 0;
101.         ArcNode* pMove = NULL;
103.         for (i = 0; i < G.vexnum; i++)
104.         {
105.                 printf("\n第%d个顶点为：%c", i + 1, G.vertices[i].data);
107.                 pMove = G.vertices[i].firstarc;
108.                 if (pMove)
109.                 {
110.                         printf("\n将第%d个顶点作为入度，与其相邻接的每个顶点在图中的位置（下标值）为：", i + 1);
111.                         while (pMove)
112.                         {
113.                                 printf("%d ", pMove->adjvex);
114.                                 pMove = pMove->nextarc;
115.                         }
116.                 }
117.                 else
118.                 {
119.                         printf("\n将第%d个顶点作为入度，没有与其相邻接的顶点。", i + 1);
120.                 }
121.         }
122. }

复制代码

接纳毗邻表表现法创建无向网

1. #include <stdio.h>
2. #include <stdlib.h>
4. #define MVNum 100
6. typedef int OtherInfo;   //假设在边结点中的数据域存储边的权值,且边的权值类型为整型
7. typedef char VerTexType;  //假设顶点的数据类型为字符型
9. typedef struct ArcNode
10. {
11.         int adjvex;
12.         struct ArcNode* nextarc;
13.         OtherInfo info;
14. }ArcNode;  //边结点
16. typedef struct VNode
17. {
18.         VerTexType data;
19.         ArcNode* firstarc;
20. }VNode, AdjList[MVNum];  //表头结点
22. typedef struct
23. {
24.         AdjList vertices;  //存储所有顶点
25.         int vexnum;  //顶点总数
26.         int arcnum;  //总边数
27. }ALGraph;  //图的信息
29. void CreateUDN(ALGraph& G);
30. int LocateVex(ALGraph& G, VerTexType v);
31. void printALGraph(ALGraph& G);
33. int main()
34. {
35.         ALGraph G = { {'\0',NULL}, 0,0 };
36.         CreateUDN(G);
37.         printALGraph(G);
39.         return 0;
40. }
42. //采用邻接表表示法创建无向网
43. void CreateUDN(ALGraph& G)
44. {
45.         int i = 0;
46.         int k = 0;
47.         VerTexType v1 = 0;
48.         VerTexType v2 = 0;
49.         int j = 0;
50.         ArcNode* p1 = NULL;
51.         ArcNode* p2 = NULL;
52.         int w = 0;
54.         printf("请输入无向网的总顶点数：");
55.         scanf_s(" %d", &G.vexnum);
57.         printf("请输入无向网的总边数：");
58.         scanf_s(" %d", &G.arcnum);
60.         for (i = 0; i < G.vexnum; ++i)
61.         {
62.                 printf("请输入第%d个顶点的值：", i + 1);
63.                 scanf_s(" %c", &(G.vertices[i].data));
64.                 G.vertices[i].firstarc = NULL;   //初始化
65.         }
67.         for (k = 0; k < G.arcnum; k++)
68.         {
69.                 printf("请输入第%d条边依附的两个顶点（用空格间隔，输入结束后按回车）: ", k + 1);
70.                 scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));               
71.                 printf("请输入第%d条边的权值 : ", k + 1);
72.                 scanf_s(" %d", &w, sizeof(OtherInfo));
74.                 i = LocateVex(G, v1);
75.                 j = LocateVex(G, v2);
77.                 p1 = (ArcNode*)malloc(sizeof(ArcNode));
78.                 p1->adjvex = j;
79.                 p1->info = w;
80.                 p1->nextarc = G.vertices[i].firstarc;
81.                 G.vertices[i].firstarc = p1;  //将新结点*p1插入顶点Vi的边表头部
83.                 p2 = (ArcNode*)malloc(sizeof(ArcNode));
84.                 p2->adjvex = i;
85.                 p1->info = w;
86.                 p2->nextarc = G.vertices[j].firstarc;
87.                 G.vertices[j].firstarc = p2;  //将与*p1对称的新的边结点*p2插入顶点Vj的边表头部
88.         }
89. }
92. //在G的顶点表vexs中获取字符v的下标（数组G.vexs的下标从0开始）
93. int LocateVex(ALGraph& G, VerTexType v)
94. {
95.         int i = 0;
96.         for (i = 0; i < G.vexnum && (G.vertices[i].data != v); ++i)
97.         {
98.                 ;
99.         }
101.         return i;
102. }
105. //打印邻接表
106. void printALGraph(ALGraph& G)
107. {
108.         int i = 0;
109.         ArcNode* pMove = NULL;
111.         for (i = 0; i < G.vexnum; i++)
112.         {
113.                 printf("\n第%d个顶点为：%c", i + 1, G.vertices[i].data);
115.                 pMove = G.vertices[i].firstarc;
116.                 if (pMove)
117.                 {
118.                         printf("\n与第%d个顶点相邻接的每个顶点在网中的位置（下标值）为：", i + 1);
119.                         while (pMove)
120.                         {
121.                                 printf("%d ", pMove->adjvex);
122.                                 pMove = pMove->nextarc;
123.                         }
124.                 }
125.                 else
126.                 {
127.                         printf("\n没有与第%d个顶点相邻接的顶点。", i + 1);
128.                 }
129.         }
130. }

复制代码

接纳毗邻表表现法创建有向网

1. #include <stdio.h>
2. #include <stdlib.h>
4. #define MVNum 100
6. typedef int OtherInfo;   //假设在边结点中的数据域存储边的权值,且边的权值类型为整型
7. typedef char VerTexType;  //假设顶点的数据类型为字符型
9. typedef struct ArcNode
10. {
11.         int adjvex;
12.         struct ArcNode* nextarc;
13.         OtherInfo info;
14. }ArcNode;  //边结点
16. typedef struct VNode
17. {
18.         VerTexType data;
19.         ArcNode* firstarc;
20. }VNode, AdjList[MVNum];  //表头结点
22. typedef struct
23. {
24.         AdjList vertices;  //存储所有顶点
25.         int vexnum;  //顶点总数
26.         int arcnum;  //总边数
27. }ALGraph;  //图的信息
29. void CreateDN(ALGraph& G);
30. int LocateVex(ALGraph& G, VerTexType v);
31. void printALGraph(ALGraph& G);
33. int main()
34. {
35.         ALGraph G = { {'\0',NULL}, 0,0 };
36.         CreateDN(G);
37.         printALGraph(G);
39.         return 0;
40. }
42. //采用邻接表表示法创建有向网
43. void CreateDN(ALGraph& G)
44. {
45.         int i = 0;
46.         int k = 0;
47.         VerTexType v1 = 0;
48.         VerTexType v2 = 0;
49.         int j = 0;
50.         ArcNode* p1 = NULL;
51.         ArcNode* p2 = NULL;
52.         int w = 0;
54.         printf("请输入有向网的总顶点数：");
55.         scanf_s(" %d", &G.vexnum);
57.         printf("请输入有向网的总边数：");
58.         scanf_s(" %d", &G.arcnum);
60.         for (i = 0; i < G.vexnum; ++i)
61.         {
62.                 printf("请输入第%d个顶点的值：", i + 1);
63.                 scanf_s(" %c", &(G.vertices[i].data));
64.                 G.vertices[i].firstarc = NULL;   //初始化
65.         }
67.         for (k = 0; k < G.arcnum; k++)
68.         {
69.                 printf("请输入第%d条边依附的两个顶点（用空格间隔，输入结束后按回车）: ", k + 1);
70.                 scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));               
71.                 printf("请输入第%d条边的权值 : ", k + 1);
72.                 scanf_s(" %d", &w, sizeof(OtherInfo));
74.                 i = LocateVex(G, v1);
75.                 j = LocateVex(G, v2);
77.                 p1 = (ArcNode*)malloc(sizeof(ArcNode));
78.                 p1->adjvex = j;
79.                 p1->info = w;
80.                 p1->nextarc = G.vertices[i].firstarc;
81.                 G.vertices[i].firstarc = p1;  //将新结点*p1插入顶点Vi的边表头部
82.         }
83. }
86. //在G的顶点表vexs中获取字符v的下标（数组G.vexs的下标从0开始）
87. int LocateVex(ALGraph& G, VerTexType v)
88. {
89.         int i = 0;
90.         for (i = 0; i < G.vexnum && (G.vertices[i].data != v); ++i)
91.         {
92.                 ;
93.         }
95.         return i;
96. }
99. //打印邻接表
100. void printALGraph(ALGraph& G)
101. {
102.         int i = 0;
103.         ArcNode* pMove = NULL;
105.         for (i = 0; i < G.vexnum; i++)
106.         {
107.                 printf("\n第%d个顶点为：%c", i + 1, G.vertices[i].data);
109.                 pMove = G.vertices[i].firstarc;
110.                 if (pMove)
111.                 {
112.                         printf("\n将第%d个顶点作为出度，与其相邻接的每个顶点在网中的位置（下标值）为：", i + 1);
113.                         while (pMove)
114.                         {
115.                                 printf("%d ", pMove->adjvex);
116.                                 pMove = pMove->nextarc;
117.                         }
118.                 }
119.                 else
120.                 {
121.                         printf("\n将第%d个顶点作为出度，没有与第%d个顶点相邻接的顶点。", i + 1);
122.                 }
123.         }
124. }

复制代码

创建有向网的逆毗邻表

1. #include <stdio.h>
2. #include <stdlib.h>
4. #define MVNum 100
6. typedef int OtherInfo;   //假设在边结点中的数据域存储边的权值,且边的权值类型为整型
7. typedef char VerTexType;  //假设顶点的数据类型为字符型
9. typedef struct ArcNode
10. {
11.         int adjvex;
12.         struct ArcNode* nextarc;
13.         OtherInfo info;
14. }ArcNode;  //边结点
16. typedef struct VNode
17. {
18.         VerTexType data;
19.         ArcNode* firstarc;
20. }VNode, AdjList[MVNum];  //表头结点
22. typedef struct
23. {
24.         AdjList vertices;  //存储所有顶点
25.         int vexnum;  //顶点总数
26.         int arcnum;  //总边数
27. }ALGraph;  //图的信息
29. void CreateDN(ALGraph& G);
30. int LocateVex(ALGraph& G, VerTexType v);
31. void printALGraph(ALGraph& G);
33. int main()
34. {
35.         ALGraph G = { {'\0',NULL}, 0,0 };
36.         CreateDN(G);
37.         printALGraph(G);
39.         return 0;
40. }
42. //创建有向网的逆邻接表
43. void CreateDN(ALGraph& G)
44. {
45.         int i = 0;
46.         int k = 0;
47.         VerTexType v1 = 0;
48.         VerTexType v2 = 0;
49.         int j = 0;
50.         ArcNode* p1 = NULL;
51.         ArcNode* p2 = NULL;
52.         int w = 0;
54.         printf("请输入有向网的总顶点数：");
55.         scanf_s(" %d", &G.vexnum);
57.         printf("请输入有向网的总边数：");
58.         scanf_s(" %d", &G.arcnum);
60.         for (i = 0; i < G.vexnum; ++i)
61.         {
62.                 printf("请输入第%d个顶点的值：", i + 1);
63.                 scanf_s(" %c", &(G.vertices[i].data));
64.                 G.vertices[i].firstarc = NULL;   //初始化
65.         }
67.         for (k = 0; k < G.arcnum; k++)
68.         {
69.                 printf("请输入第%d条边依附的两个顶点（用空格间隔，输入结束后按回车）: ", k + 1);
70.                 scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));
71.                 printf("请输入第%d条边的权值 : ", k + 1);
72.                 scanf_s(" %d", &w, sizeof(OtherInfo));
74.                 i = LocateVex(G, v1);
75.                 j = LocateVex(G, v2);
77.                 p1 = (ArcNode*)malloc(sizeof(ArcNode));
78.                 p1->adjvex = i;
79.                 p1->info = w;
80.                 p1->nextarc = G.vertices[j].firstarc;
81.                 G.vertices[j].firstarc = p1;  //将新结点*p1插入顶点Vj的边表头部
82.         }
83. }
86. //在G的顶点表vexs中获取字符v的下标（数组G.vexs的下标从0开始）
87. int LocateVex(ALGraph& G, VerTexType v)
88. {
89.         int i = 0;
90.         for (i = 0; i < G.vexnum && (G.vertices[i].data != v); ++i)
91.         {
92.                 ;
93.         }
95.         return i;
96. }
99. //打印逆邻接表
100. void printALGraph(ALGraph& G)
101. {
102.         int i = 0;
103.         ArcNode* pMove = NULL;
105.         for (i = 0; i < G.vexnum; i++)
106.         {
107.                 printf("\n第%d个顶点为：%c", i + 1, G.vertices[i].data);
109.                 pMove = G.vertices[i].firstarc;
110.                 if (pMove)
111.                 {
112.                         printf("\n将第%d个顶点作为入度，与其相邻接的每个顶点在网中的位置（下标值）为：", i + 1);
113.                         while (pMove)
114.                         {
115.                                 printf("%d ", pMove->adjvex);
116.                                 pMove = pMove->nextarc;
117.                         }
118.                 }
119.                 else
120.                 {
121.                         printf("\n将第%d个顶点作为入度，没有与第%d个顶点相邻接的顶点。", i + 1);
122.                 }
123.         }
124. }

复制代码

6.4.3 十字链表

接纳十字链表表现法创建有向图

1. //采用十字链表表示法创建有向图
3. #include <stdio.h>
4. #include <stdlib.h>
6. #define MAX_VERTEX_NUM  20
8. typedef int InfoType;   //假设在边结点中的数据域存储边的权值,且边的权值类型为整型
9. typedef char VerTexType;  //假设顶点的数据类型为字符型
11. typedef struct ArcBox
12. {
13.         int tailvext;
14.         int headvex;
15.         struct ArcBox* hlink;
16.         struct ArcBox* tlink;
17.         InfoType *info;
18. }ArcBox;  
20. typedef struct VexNode
21. {
22.         VerTexType data;
23.         ArcBox *firstin;
24.         ArcBox *firstout;
25. }VexNode;
27. typedef struct
28. {
29.         VexNode xlist[MAX_VERTEX_NUM];  //表头向量
30.         int vexnum;  //顶点总数
31.         int arcnum;  //总边数
32. }OLGraph;  //图的信息
34. void CreateOLGraph(OLGraph& G);
35. int LocateVex(OLGraph& G, VerTexType v);
36. void printOLGraph(OLGraph& G);
38. int main()
39. {
40.         OLGraph G = { {'\0',NULL,NULL}, 0,0 };
41.         CreateOLGraph(G);
42.         printOLGraph(G);
44.         return 0;
45. }
47. //采用十字链表表示法创建有向图
48. void CreateOLGraph(OLGraph& G)
49. {
50.         int i = 0;
51.         int j = 0;
52.         int k = 0;
53.         VerTexType v1 = 0;
54.         VerTexType v2 = 0;
55.         ArcBox* p1 = NULL;
58.         printf("请输入有向图的总顶点数：");
59.         scanf_s(" %d", &G.vexnum);
61.         printf("请输入有向图的总边数：");
62.         scanf_s(" %d", &G.arcnum);
64.         for (i = 0; i < G.vexnum; ++i)
65.         {
66.                 printf("请输入第%d个顶点的值：", i + 1);
67.                 scanf_s(" %c", &(G.xlist[i].data));
68.                 G.xlist[i].firstin = NULL;
69.                 G.xlist[i].firstout = NULL;//初始化
70.         }
72.         for (k = 0; k < G.arcnum; k++)
73.         {
74.                 printf("请输入第%d条弧依附的两个顶点（用空格间隔，输入结束后按回车）: ", k + 1);
75.                 scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));
76.                 //起点v1是弧尾，终点v2是弧头
77.                 //弧<v1,v2>是v1的出度，是v2的入度
79.                 i = LocateVex(G, v1);
80.                 j = LocateVex(G, v2);
81.                 //起点v1是弧尾，下标值为i；终点v2是弧头，下标值为j
82.                 //弧<v1,v2>是第i+1个顶点的出度firstout，是第j+1个顶点的入度firstin
84.                 p1 = (ArcBox*)malloc(sizeof(ArcBox));
86.                 p1->tailvext = i;  //起点v1是弧尾，下标值为i
87.                 p1->headvex = j;   //终点v2是弧头，下标值为j
89.                 //p1弧结点中的链域tlink指向与其弧尾tailvext相同的下一条弧（即指向第i+1个顶点v1的下一个出度firstout）
90.                 p1->tlink = G.xlist[i].firstout;  //p1指向的弧<v1,v2>是第i+1个顶点v1的出度firstout
91.                 G.xlist[i].firstout = p1;   //前插法将p1插入到第i+1个顶点v1的出度单链表中
93.                 //p1弧结点中的链域hlink指向与其弧头headvex相同的下一条弧（即指向第j+1个顶点v2的下一个入度firstin）
94.                 p1->hlink = G.xlist[j].firstin;   //p1指向的弧<v1,v2>是第j+1个顶点v2的入度firstin
95.                 G.xlist[j].firstin = p1;  //前插法将p1插入到第j+1个顶点v2的入度单链表中
96.         }
97. }
100. //在G的顶点表xlist中获取字符v的下标（数组G.xlist的下标从0开始）
101. int LocateVex(OLGraph& G, VerTexType v)
102. {
103.         int i = 0;
104.         for (i = 0; i < G.vexnum && (G.xlist[i].data != v); ++i)
105.         {
106.                 ;
107.         }
109.         return i;
110. }
113. //打印十字链表
114. void printOLGraph(OLGraph& G)
115. {
116.         int i = 0;
117.         ArcBox* pMoveIn = NULL;
118.         ArcBox* pMoveOut = NULL;
120.         for (i = 0; i < G.vexnum; i++)
121.         {
122.                 printf("\n第%d个顶点为：%c", i + 1, G.xlist[i].data);
124.                 pMoveOut = G.xlist[i].firstout;
125.                 if (pMoveOut)
126.                 {
127.                         printf("\n将第%d个顶点作为出度，与其相邻接的每个顶点在图中的位置（下标值）为：", i + 1);
128.                         while (pMoveOut)
129.                         {
130.                                 printf("%d ", pMoveOut->headvex);
131.                                 pMoveOut = pMoveOut->tlink;
132.                         }
133.                 }
134.                 else
135.                 {
136.                         printf("\n将第%d个顶点作为出度，没有与其相邻接的顶点。", i + 1);
137.                 }
140.                 pMoveIn = G.xlist[i].firstin;
141.                 if (pMoveIn)
142.                 {
143.                         printf("\n将第%d个顶点作为入度，与其相邻接的每个顶点在图中的位置（下标值）为：", i + 1);
144.                         while (pMoveIn)
145.                         {
146.                                 printf("%d ", pMoveIn->tailvext);
147.                                 pMoveIn = pMoveIn->hlink;
148.                         }
149.                 }
150.                 else
151.                 {
152.                         printf("\n将第%d个顶点作为入度，没有与其相邻接的顶点。", i + 1);
153.                 }
155.         }
156. }

复制代码

   该有向图的毗邻矩阵，其中各行、各列中不为0的元素，与其十字链表每个顶点的出度、入度效果有对应关系。

  接纳十字链表表现法创建有向网

   输入并读取权值，赋值到 弧结点 ArcBox 布局中的 info 成员即可。

1. //采用十字链表表示法创建有向网
3. void CreateOLGraph(OLGraph& G)
4. {
5.         int i = 0;
6.         int j = 0;
7.         int k = 0;
8.         VerTexType v1 = 0;
9.         VerTexType v2 = 0;
10.         ArcBox* p1 = NULL;
12.         int* w = 0;
14.         printf("请输入有向网的总顶点数：");
15.         scanf_s(" %d", &G.vexnum);
17.         printf("请输入有向网的总边数：");
18.         scanf_s(" %d", &G.arcnum);
20.         for (i = 0; i < G.vexnum; ++i)
21.         {
22.                 printf("请输入第%d个顶点的值：", i + 1);
23.                 scanf_s(" %c", &(G.xlist[i].data));
24.                 G.xlist[i].firstin = NULL;
25.                 G.xlist[i].firstout = NULL;//初始化
26.         }
28.         for (k = 0; k < G.arcnum; k++)
29.         {
30.                 printf("请输入第%d条弧依附的两个顶点（用空格间隔，输入结束后按回车）: ", k + 1);
31.                 scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));
33.                 printf("请输入第%d条边的权值 : ", k + 1);
34.                 scanf_s(" %d", w, sizeof(InfoType));  //在ArcBox中，info由指向int的指针定义
36.                 i = LocateVex(G, v1);
37.                 j = LocateVex(G, v2);
39.                 p1 = (ArcBox*)malloc(sizeof(ArcBox));
41.                 p1->tailvext = i;
42.                 p1->headvex = j;  
44.                 p1->info = w;  //赋值到弧结点p1中的info成员
46.                 p1->tlink = G.xlist[i].firstout;  
47.                 G.xlist[i].firstout = p1;   
49.                 p1->hlink = G.xlist[j].firstin;   
50.                 G.xlist[j].firstin = p1;  
51.         }
52. }

复制代码

6.4.4 毗邻多重表

接纳毗邻多重表表现法创建无向图

1. //采用邻接多重表表示法创建无向图
3. #include <stdio.h>
4. #include <stdlib.h>
6. #define MAX_VERTEX_NUM  20
8. typedef enum {unvisited,visited} VisitIf;
9. typedef int InfoType;   //假设在边结点中的数据域存储边的权值,且边的权值类型为整型
10. typedef char VerTexType;  //假设顶点的数据类型为字符型
12. typedef struct EBox
13. {
14.         VisitIf mark;
15.         int ivex;
16.         int jvex;
17.         struct EBox* ilink;
18.         struct EBox* jlink;
19.         InfoType *info;
20. }EBox;  
22. typedef struct VexBox
23. {
24.         VerTexType data;
25.         EBox* firstedge;
26. }VexBox;
28. typedef struct
29. {
30.         VexBox adjmulist[MAX_VERTEX_NUM];  //表头向量
31.         int vexnum;  //顶点总数
32.         int edgenum;  //总边数
33. }AMLGraph;  //图的信息
35. void CreateAMLGraph(AMLGraph& G);
36. int LocateVex(AMLGraph& G, VerTexType v);
37. void printAMLGraph(AMLGraph& G);
39. int main()
40. {
41.         AMLGraph G = { {'\0',NULL,NULL}, 0,0 };
42.         CreateAMLGraph(G);
43.         printAMLGraph(G);
45.         return 0;
46. }
48. //采用邻接多重表表示法创建无向图
49. void CreateAMLGraph(AMLGraph& G)
50. {
51.         int i = 0;
52.         int j = 0;
53.         int k = 0;
54.         VerTexType v1 = 0;
55.         VerTexType v2 = 0;
56.         EBox* p1 = NULL;
58.         printf("请输入无向图的总顶点数：");
59.         scanf_s(" %d", &G.vexnum);
61.         printf("请输入无向图的总边数：");
62.         scanf_s(" %d", &G.edgenum);
64.         for (i = 0; i < G.vexnum; ++i)
65.         {
66.                 printf("请输入第%d个顶点的值：", i + 1);
67.                 scanf_s(" %c", &(G.adjmulist[i].data));
68.                 G.adjmulist[i].firstedge = NULL;  //初始化
69.         }
71.         for (k = 0; k < G.edgenum; k++)
72.         {
73.                 printf("请输入第%d条弧依附的两个顶点（用空格间隔，输入结束后按回车）: ", k + 1);
74.                 scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));
75.                
76.                 i = LocateVex(G, v1);
77.                 j = LocateVex(G, v2);
79.                 p1 = (EBox*)malloc(sizeof(EBox));
81.                 p1->ivex = i;
82.                 p1->jvex = j;  
84.                 p1->ilink = G.adjmulist[i].firstedge;
85.                 G.adjmulist[i].firstedge = p1;
87.                 p1->jlink = G.adjmulist[j].firstedge;
88.                 G.adjmulist[j].firstedge = p1;
89.         }
90. }
93. //在G的顶点表adjmulist中获取字符v的下标（数组G.xlist的下标从0开始）
94. int LocateVex(AMLGraph& G, VerTexType v)
95. {
96.         int i = 0;
97.         for (i = 0; i < G.vexnum && (G.adjmulist[i].data != v); ++i)
98.         {
99.                 ;
100.         }
102.         return i;
103. }
106. //打印邻接多重表
107. void printAMLGraph(AMLGraph& G)
108. {
109.         int i = 0;
110.         EBox* pMove = NULL;
112.         for (i = 0; i < G.vexnum; i++)
113.         {
114.                 printf("\n第%d个顶点为：%c", i + 1, G.adjmulist[i].data);
115.                 pMove = G.adjmulist[i].firstedge;
117.                 if (pMove)
118.                 {
119.                         printf("\n与第%d个顶点相邻接的每个顶点在图中的位置（下标值）为：", i + 1);
120.                         while (pMove)
121.                         {
122.                                 if (pMove->ivex == i)
123.                                 {
124.                                         printf("%d ", pMove->jvex);
125.                                         pMove = pMove->ilink;
126.                                 }
127.                                 else if (pMove->jvex == i)
128.                                 {
129.                                         printf("%d ", pMove->ivex);
130.                                         pMove = pMove->jlink;
131.                                 }
132.                         }
133.                 }
134.                 else
135.                 {
136.                         printf("\n没有与第%d个顶点相邻接的顶点。", i + 1);
137.                 }       
138.         }
139. }

复制代码

接纳毗邻多重表表现法创建无向网

   输入并读取权值，赋值到 边结点 EBox 布局中的 info 成员即可。

1. //采用邻接多重表表示法创建无向网
2. void CreateAMLGraph(AMLGraph& G)
3. {
4.         int i = 0;
5.         int j = 0;
6.         int k = 0;
7.         VerTexType v1 = 0;
8.         VerTexType v2 = 0;
9.         EBox* p1 = NULL;
11.         int* w = 0;
13.         printf("请输入无向网的总顶点数：");
14.         scanf_s(" %d", &G.vexnum);
16.         printf("请输入无向网的总边数：");
17.         scanf_s(" %d", &G.edgenum);
19.         for (i = 0; i < G.vexnum; ++i)
20.         {
21.                 printf("请输入第%d个顶点的值：", i + 1);
22.                 scanf_s(" %c", &(G.adjmulist[i].data));
23.                 G.adjmulist[i].firstedge = NULL;  //初始化
24.         }
26.         for (k = 0; k < G.edgenum; k++)
27.         {
28.                 printf("请输入第%d条弧依附的两个顶点（用空格间隔，输入结束后按回车）: ", k + 1);
29.                 scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));
31.                 printf("请输入第%d条边的权值 : ", k + 1);
32.                 scanf_s(" %d", w, sizeof(InfoType));  //在EBox中，info由指向int的指针定义
34.                 i = LocateVex(G, v1);
35.                 j = LocateVex(G, v2);
37.                 p1 = (EBox*)malloc(sizeof(EBox));
39.                 p1->ivex = i;
40.                 p1->jvex = j;  
42.                 p1->info = w;   //赋值到边结点p1中的info成员
44.                 p1->ilink = G.adjmulist[i].firstedge;
45.                 G.adjmulist[i].firstedge = p1;
47.                 p1->jlink = G.adjmulist[j].firstedge;
48.                 G.adjmulist[j].firstedge = p1;
49.         }
50. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。