都两天了。大家帮帮我呀～关于图遍历的。谢谢了。

lluct

深度遍历没有遍历全，而广度遍历却"跳着"遍历。

2. #include <stdio.h>;
3. #define vnum 20
5. typedef struct arcnode
6. {
7.   int adjvex;
8.   struct arcnode *nextarc;
9. } ArcNodeTp;
11. typedef struct vexnode
12. {
13.   int vertex;
14.   ArcNodeTp *firstarc;
15. } AdjList[vnum];
17. typedef struct linkgraph
18. {
19.   AdjList adjs;
20.   int vexnum, arcnum;
21. } LGraphTp;
23. typedef struct linked_queue
24. {
25.   int data;
26.   struct linked_queue *next;
27. } LqueueTp;
29. typedef struct queueptr
30. {
31.   LqueueTp *front, *rear;
32. } QueptrTp;
35. LGraphTp* Create_LNvGraph (LGraphTp *ga);
37. int main (void)
38. {
39.   LGraphTp *ga;
40.   int input, choose;
41.   ga = (LGraphTp *) malloc (sizeof(LGraphTp));
42.   ga = Create_LNvGraph(ga);
43.   Print_LinkList(ga);
44.   printf("\n1:深度优先搜索 2:广度优先搜索 3,返回:");
45.   scanf("%d", &choose);
46.   switch (choose)
47.     {
48.     case 1:
49.       printf("\n%s\n%s", "###深度优先搜索###", "请问要搜索的结点号:");
50.       scanf("%d", &input);
51.       DFS(ga, input);
52.       break;
53.     case 2:
54.       printf("\n%s\n%s", "###广度优先搜索###", "请问要搜索的结点号:");
55.       scanf("%d", &input);
56.       BFS(ga, input);
57.       break;
58.     case 3:
59.       break;
60.     default:
61.       printf("\n选择错误!\n");
62.     }
63.   printf("\n\n");
64. }
66. LGraphTp* Create_LNvGraph (LGraphTp *ga)
67. {
68.   ArcNodeTp *p;
69.   int vex, arc, vexs, arcnum;
70.   int i, j, k;
72.   printf("\n无向图邻接表\n");
73.   printf("请输入顶点个数:");
74.   scanf("%d", &vex);
75.   printf("请输入边数个数:");
76.   scanf("%d", &arc);
77.   ga ->; vexnum = vex;
78.   ga ->; arcnum = arc;
80.   for (i = 0; i < ga ->; vexnum; i++)
81.     {
82.       ga ->; adjs[i].vertex = i + 1;
83.       ga ->; adjs[i].firstarc = NULL;
84.     }
86.   for (k = 0; k < arc; k++)
87.     {
88.       printf("请输入第%d条边两个顶点的编号:", k + 1);
89.       scanf("%d %d", &i, &j);
90.       p = (ArcNodeTp *) malloc (sizeof(ArcNodeTp));
91.       p ->; adjvex = j;
92.       p ->; nextarc = ga ->; adjs[i - 1].firstarc;
93.       ga ->; adjs[i - 1].firstarc = p;
94.       p = (ArcNodeTp *) malloc (sizeof(ArcNodeTp));
95.       p ->; adjvex = i;
96.       p ->; nextarc = ga ->; adjs[j - 1].firstarc;
97.       ga ->; adjs[j - 1].firstarc = p;
98.     }
99.   return (ga);
100. }
102. int Print_LinkList (LGraphTp *ga)
103. {
104.   ArcNodeTp *p;
105.   int k;
106.   printf("\n目前输入的邻接表为:\n\n");
107.   
108.   for (k = 0; k < ga ->; vexnum; k++)
109.     {
110.       printf("V%d:%d |", k + 1, ga ->; adjs[k].vertex);
111.       p = ga ->; adjs[k].firstarc;
112.       while (p != NULL)
113.         {
114.           printf(" ->; %d", p ->; adjvex);
115.           p = p ->; nextarc;
116.         }
117.       printf("\n");
118.     }
119. }
121. int DFS (LGraphTp *ga, int v)
122. {
123.   ArcNodeTp *p;
124.   int j;
125.   static int visited[vnum];
127.   for (j = 0; j < vnum; j++)
128.     visited[vnum] = 0;
130.   printf(" ->; %d ", v);
131.   visited[v] = 1;
132.   p = ga ->; adjs[v].firstarc;
133.   while (p != NULL)
134.     {
135.       if (! visited[p ->; adjvex])
136.         DFS(ga, p ->; adjvex);
137.       p = p ->; nextarc;
138.     }
139. }
141. int InitQueue (QueptrTp **lq)
142. {
143.   LqueueTp *p;
144.   p = (LqueueTp *) malloc (sizeof(LqueueTp));
145.   (*lq) ->; front = p;
146.   (*lq) ->; rear = p;
147.   ((*lq) ->; front)  ->; next = NULL;
148. }
150. int EnQueue (QueptrTp **lq, int x)
151. {
152.   LqueueTp *p;
153.   p = (LqueueTp *) malloc (sizeof(LqueueTp));
154.   p ->; data = x;
155.   p ->; next = NULL;
156.   ((*lq) ->; rear) ->; next = p;
157.   (*lq) ->; rear = p;
158. }
160. int OutQueue (QueptrTp **lq, int *x)
161. {
162.   LqueueTp *s;
163.   if ((*lq) ->; front == (*lq) ->; rear)
164.     {
165.       printf("队空!\n");
166.       return 0;
167.     }
168.   else
169.     {
170.     s = ((*lq) ->; front) ->; next;
171.     *x = s ->; data;
172.     ((*lq) ->; front) ->; next = s ->; next;
173.     if (s ->; next == NULL)
174.       (*lq) ->; rear = (*lq) ->; front;
175.     free(s);
176.     return 1;
177.     }
178. }
180. int EmptyQueue (QueptrTp **lq)
181. {
182.   if (((*lq) ->; rear) == ((*lq) ->; front))
183.     return 1;
184.   else
185.     return 0;
186. }
188. int GetHead (QueptrTp **lq, int *x)
189. {
190.   LqueueTp *p;
191.   if ((*lq) ->; rear == (*lq) ->; front)
192.     return 0;
193.   else
194.     {
195.       p = ((*lq) ->; front ) ->; next;
196.       *x = p ->; data;
197.       return 1;
198.     }
200. }  
202. int BFS(LGraphTp *ga, int v)
203. {
204.   QueptrTp *Q;
205.   static int visited[vnum];
206.   ArcNodeTp *p;
207.   InitQueue(&Q);
208.   printf("%d", v);
209.   visited[v] = 1;
210.   EnQueue(&Q, v);
211.   while (! EmptyQueue(&Q))
212.     {
213.       OutQueue(&Q, &v);
214.       p = ga ->; adjs[v].firstarc;
215.       while (p != NULL)
216.         {
217.           if (! visited[p ->; adjvex])
218.             {
219.               printf("%d", p ->; adjvex);
220.               visited[p ->; adjvex] = 1;
221.               EnQueue(&Q, p ->; adjvex);
222.             }
223.           p = p ->; nextarc;
224.         }
225.     }
226. }

复制代码

lenovo

没时间帮你看。
这程序是你写的还是抄的书上的？
很多数据结构书上都有代码的，
参考一下把。

lluct

原帖由 "lenovo" 发表：
没时间帮你看。
这程序是你写的还是抄的书上的？
很多数据结构书上都有代码的，
参考一下把。

书上只给出伪代码。

lenovo

那就找一本有源代码的，
或者仔细检查你的源码和伪码之间的差别。