广度优先搜索c++代码（广度优先搜索代码c语言实现）



 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 } 

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/cjjbc/18056.html