1 图论：最短路径（广度优先搜索、C语言实现）
2 要用到的数据结构有：
3 队列、表、邻接表
4 分为六个文件-
5 |–Main.c 应用文件：main函数所在。读取各边到邻接表，然后调用计算机最小路径函数。求解。
6 |–code.c 最小路径函数：最小路径函数所在。
7 |–Queue.c 数据结构：队列
8 |–Table.c 数据结构：表
9 |–AdjList.c数据结构：邻接表
10 |–Graph.h 将所有数据结构文件包含进来
11
12 邻接表和队列的源泉代码可以从文章列表中找到。
13 算法为广度优先搜索。将路径和点记录在一张表中。最后用打印函数递归的打印出路径。思路可见《数据结构与算法分析》。
14 各文件源代码如下：
15 图论：最短路径（广度优先搜索、C语言实现） 16 要用到的数据结构有： 17 队列、表、邻接表 18 分为六个文件- 19 |–Main.c 应用文件：main函数所在。读取各边到邻接表，然后调用计算机最小路径函数。求解。 20 |–code.c 最小路径函数：最小路径函数所在。 21 |–Queue.c 数据结构：队列 22 |–Table.c 数据结构：表 23 |–AdjList.c数据结构：邻接表 24 |–Graph.h 将所有数据结构文件包含进来 25 26 邻接表和队列的源泉代码可以从文章列表中找到。 27 算法为广度优先搜索。将路径和点记录在一张表中。最后用打印函数递归的打印出路径。思路可见《数据结构与算法分析》。 28 各文件源代码如下： 29 [cpp] view plaincopyprint? 30 Graph.h:#ifndef _Graph_h
31 #include “Queue.c”
32 #include “Table.c”
33 #endif
34 Graph.h:#ifndef _Graph_h 35 #include “Queue.c” 36 #include “Table.c” 37 #endif [cpp] view plaincopyprint? 38 Main.c:
39 #include “code.c”
40 int main()
41 {
42 Vertex Graph = NULL ; Table T ;
43 int x, y, s, a ;
44 /读取各边并插入/
45 for(scanf(“%d %d”, &x, &y); x != -1 ; scanf(“%d %d”, &x, &y))
46 Graph = InsertEdge(x, y, Graph) ;
47 /创建用于簿记的表，并初化始表：将图中各点格式化入表中/
48 T = CreatTable(SizeOfGraph(Graph)) ;
49 TableInit(T, Graph) ;
50 /获取起点/
51 printf(“Input the start vertex: ”) ;
52 scanf(“%d”, &s) ;
53 /计算各点的最短路径，并记录表中/
54 ShortestPath(s, Graph, T) ;
55 /得到终点/
56 printf(“Input the aim vertex: ”) ;
57 scanf(“%d”, &a) ;
58 /打印出该路径，未尾会/
59 TablePrint(s, a, T) ;
60 printf(“ ”) ;
61 /释放内存/
62 GraphDestory(Graph) ;
63 TableDestory(T) ;
64
65 return 0;
66 }
67 Main.c: 68 #include “code.c” 69 int main() 70 { 71 Vertex Graph = NULL ; Table T ; 72 int x, y, s, a ; 73 /读取各边并插入/ 74 for(scanf(“%d %d”, &x, &y); x != -1 ; scanf(“%d %d”, &x, &y)) 75 Graph = InsertEdge(x, y, Graph) ; 76 /创建用于簿记的表，并初化始表：将图中各点格式化入表中/ 77 T = CreatTable(SizeOfGraph(Graph)) ; 78 TableInit(T, Graph) ; 79 /获取起点/ 80 printf(“Input the start vertex: ”) ; 81 scanf(“%d”, &s) ; 82 /计算各点的最短路径，并记录表中/ 83 ShortestPath(s, Graph, T) ; 84 /得到终点/ 85 printf(“Input the aim vertex: ”) ; 86 scanf(“%d”, &a) ; 87 /打印出该路径，未尾会/ 88 TablePrint(s, a, T) ; 89 printf(“ ”) ; 90 /释放内存/ 91 GraphDestory(Graph) ; 92 TableDestory(T) ; 93 94 return 0; 95 }[cpp] view plaincopyprint? 96 code.c:
97 #include “Graph.h”
98
99 void ShortestPath(int S, Vertex Graph, Table T)
100 {
101 Queue Q ; int NumVertex ;
102 int tmp ; int V, W ;
103 Ind_Node Ind ; int DistCount = 0;
104 //init what should be init 105 /计算图中的点数/
106 NumVertex = SizeOfGraph(Graph) ;
107 /创建队列/
108 Q = CreatQueue(NumVertex) ;
109 //enter the start vertex into queue 110 /找到起点/
111 tmp = TableFind(S, T) ;
112 /初始化起点/
113 T->Array[tmp].Know = True ;
114 T->Array[tmp].Path = 0 ;
115 T->Array[tmp].Dist = 0 ;
116 /将起点推入队列之中，以驱动下面的代码/
117 Enqueue(tmp, Q) ;
118 /第一次运行至此，队列不为空，因为插入起点/
119 while(!QueueIsEmpty(Q))
120 {
121 /读取一点/
122 V = Dequeue(Q) ;
123 /读取V的各个入度/
124 Ind = (T->Array[V].prototype)->Indegree ;
125 while(Ind != NULL)
126 {
127 /W为当前读取到的入度点/
128 W = TableFind(Ind->Number, T) ;
129 if(T->Array[W].Dist == Infinity)
130 {
131 /如果W以前没有处理过，那么进行处理/
132 T->Array[W].Dist = T->Array[V].Dist +1 ;
133 T->Array[W].Path = (T->Array[V].prototype)->Number ;
134 /然后推入队列之中/
135 Enqueue(W, Q) ;
136 }
137 /处理下一入度点/
138 Ind = Ind->Next ;
139 }
140 }
141 /
142 QueueDestory(Q) ;
143 }
144 code.c: 145 #include “Graph.h” 146 147 void ShortestPath(int S, Vertex Graph, Table T) 148 { 149 Queue Q ; int NumVertex ; 150 int tmp ; int V, W ; 151 Ind_Node Ind ; int DistCount = 0; 152 //init what should be init 153 /计算图中的点数/ 154 NumVertex = SizeOfGraph(Graph) ; 155 /创建队列/ 156 Q = CreatQueue(NumVertex) ; 157 //enter the start vertex into queue 158 /找到起点/ 159 tmp = TableFind(S, T) ; 160 /初始化起点/ 161 T->Array[tmp].Know = True ; 162 T->Array[tmp].Path = 0 ; 163 T->Array[tmp].Dist = 0 ; 164 /将起点推入队列之中，以驱动下面的代码/ 165 Enqueue(tmp, Q) ; 166 /第一次运行至此，队列不为空，因为插入起点/ 167 while(!QueueIsEmpty(Q)) 168 { 169 /读取一点/ 170 V = Dequeue(Q) ; 171 /读取V的各个入度/ 172 Ind = (T->Array[V].prototype)->Indegree ; 173 while(Ind != NULL) 174 { 175 /W为当前读取到的入度点/ 176 W = TableFind(Ind->Number, T) ; 177 if(T->Array[W].Dist == Infinity) 178 { 179 /如果W以前没有处理过，那么进行处理/ 180 T->Array[W].Dist = T->Array[V].Dist +1 ; 181 T->Array[W].Path = (T->Array[V].prototype)->Number ; 182 /然后推入队列之中/ 183 Enqueue(W, Q) ; 184 } 185 /处理下一入度点/ 186 Ind = Ind->Next ; 187 } 188 } 189 / 190 QueueDestory(Q) ; 191 }[cpp] view plaincopyprint? 192
193 [cpp] view plaincopyprint? 194 Table.c:
195 #include <stdio.h>
196 #include <stdlib.h>
197 #include “AdjList.c”
198 #include “limits.h”
199 #define Infinity INT_MAX
200 #define True 1
201 #define False 0
202 typedef struct table_element_tag
203 {
204 /将向邻接表中的点/
205 Vertex prototype ;
206 /路径长度/
207 int Dist ;
208 /记录该点在最短路径中的上一个点。/
209 int Path ;
210 }TableElement ;
211 typedef struct table_tag
212 {
213 /这里是表头，第一个是记录表大小，第二个是数组（数组实现表）/
214 int Size ;
215 TableElement Array ;
216 }Table ;
217
218 Table CreatTable(int Max)
219 {
220 /分配好内存，返回/
221 Table T ;
222 T = calloc(1, sizeof(struct table_tag)) ;
223 if(!T) { fprintf(stderr, “Out of space! ”); exit(1) ;}
224 T->Array = calloc(Max, sizeof(struct table_element_tag)) ;
225 if(!T->Array){ fprintf(stderr, “Out of space!”) ; exit(1) ;}
226 T->Size = Max ;
227 return T ;
228 }
229 void TableInit(Table T, Vertex Graph)
230 {
231 /将表中各点记录表中/
232 int i = 0;
233 while(Graph != NULL && i < T->Size)
234 {
235 //calloc will init Know 236 T->Array[i].prototype = Graph ;
237 /记录为无穷大，表示该点未知/
238 T->Array[i].Dist = Infinity ;
239 T->Array[i].Path = Infinity ;
240 i++ ;
241 Graph = Graph->Next ;
242 }
243 }
244 int TableFind(int f, Table T)
245 {
246 TableElement te ; int size ; int i ;
247 if(!T){ fprintf(stderr, “Graph was empty or miss! ”) ; exit(1) ;}
248 te = T->Array ; size = T->Size ;
249 for( i = 0; i < size; i++)
250 if( (te[i].prototype)->Number == f)
251 break ;
252 if(i < size)
253 return i ;
254 else /如果没有找到就返回无穷大/
255 return Infinity ;
256 }
257 void TablePrint(int s, int a, Table T)
258 {
259 int tmp ;
260 if(a != s)
261 {
262 tmp = TableFind(a, T) ;
263 if(tmp == Infinity){ fprintf(stderr, “No Found the vertex: %d ”, a) ; exit(1) ;}
264 TablePrint(s, T->Array[tmp].Path, T) ;
265 printf(“ to ”) ;
266 }
267 printf(“%d”, (T->Array[TableFind(a, T)].prototype)->Number) ;
268 }
269 void TableDestory(Table T)
270 {
271 /释放内存/
272 if(T)
273 {
274 if(T->Array)
275 free(T->Array) ;
276 free(T) ;
277 }
278 }
讯享网
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/196678.html