그림 이론: 최 단 경로: 범위 우선 검색 (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    
196 #include    
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 }