06-圖1 列出連通集 (25分)（C語言鄰接表實現），06-鄰接
題目地址：https://pta.patest.cn/pta/test/558/exam/4/question/9495
由於邊數E<(n*(n-1))/2 所以我選用了鄰接表實現，優先隊列用循環隊列實現；
DFS基本思路：
1：選擇一個點，標志已經訪問過；
2：判斷這個點的其他鄰接點（訪問順序按題目是從小到大）是否訪問過，來選擇下一個點；
3：重復第2點知道全部點已經訪問過。
偽代碼如下
DFS( Vertex v )
{
Visit( V );
Visited[V] = true;
foreach( v->neighbor )
if ( Visited[v->neighbor ] == false )
DFS(v->neighbor );
}
BFS基本思路：
1：選擇一個點入隊，並訪問這個點，標志已經訪問過；
2：出隊，將這個點未訪問過的全部鄰點訪問並入隊；
3：重復第二點直到隊列為空；
偽代碼如下
BFS ( Vertex v )
{
Visit( v );
Visited[v] = true;
EnQueue(Q, v);
while ( !IsEmpty(Q) )
{
w = DeQueue(Q);
foreach ( w->neighor )
if ( Visited[w->neighor] == false )
{
Visit( w->neighor );
Visited[w->neighor] = true;
EnQueue(Q, w->neighor);
}
}
}
具體代碼
![]()
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <stdbool.h>
4 #include <string.h>
5 #include <dos.h>
6
7 #define MaxVertexNum 10
8
9 typedef int ElementType;
10 typedef int Position;
11
12 typedef struct QNode {
13 ElementType *Data; /* 存儲元素的數組 */
14 Position Front, Rear; /* 隊列的頭、尾指針 */
15 int MaxSize; /* 隊列最大容量 */
16 }QNode, *Queue;
17
18
19 typedef struct ENode
20 {
21 int ivex; //該邊指向的頂點位置
22 struct ENode * next;
23 }ENode, *PENode;
24
25 typedef int VertexType;
26
27 typedef struct VNode
28 {
29 VertexType data;
30 ENode * first_edge;
31 }VNode;
32
33 typedef struct LGraph
34 {
35 int vexnum; //圖的頂點數目
36 int edgnum; //圖的邊的數目
37 VNode * vexs; //存放頂點的數組
38 }LGraph;
39
40 bool TAG; //用於輸出格式
41 bool visited[MaxVertexNum];
42
43 LGraph * LGraph_new();
44 void LGraph_destroy(LGraph * G);
45 void LGraph_insert(ENode ** head, int ivex);
46 void ResetVisit();
47 void DFS(LGraph * G, int vex);
48 void BFS(LGraph * G, int vex);
49 void ListComponents(LGraph * G, void (*func)(LGraph * G, int vex));
50
51 //優先隊列的基本操作
52 Queue CreateQueue( int MaxSize );
53 bool IsFull( Queue Q );
54 bool AddQ( Queue Q, ElementType X );
55 bool IsEmpty( Queue Q );
56 ElementType DeleteQ( Queue Q );
57
58 int main()
59 {
60 LGraph * G = LGraph_new();
61 ResetVisit();
62 ListComponents(G, DFS);
63 ResetVisit();
64 ListComponents(G, BFS);
65 system("pause");
66 return 0;
67 }
68
69 void ListComponents(LGraph * G, void (*func)(LGraph * G, int vex))
70 {
71 int i;
72 for ( i = 0; i < G->vexnum; ++i )
73 {
74 if (visited[i] == false)
75 {
76 (*func)(G, i);
77 printf("}\n");
78 TAG = false;
79 }
80 }
81 }
82
83 LGraph * LGraph_new()
84 {
85
86 LGraph * G = (LGraph *)malloc(sizeof(LGraph));
87 scanf("%d %d", &G->vexnum, &G->edgnum);
88 G->vexs = (VNode *)malloc(G->vexnum * sizeof(VNode));
89 int i, v1, v2;
90 for ( i = 0; i < G->vexnum; ++i )
91 {
92 G->vexs[i].data = i;
93 G->vexs[i].first_edge = NULL;
94 }
95 for ( i = 0; i < G->edgnum; ++i )
96 {
97 scanf("%d %d", &v1, &v2);
98 //由於頂點信息就是頂點坐標
99 LGraph_insert(&G->vexs[v1].first_edge, v2);
100 LGraph_insert(&G->vexs[v2].first_edge, v1);
101 }
102 return G;
103 }
104
105 void ResetVisit()
106 {
107 TAG = false;
108 memset(visited, false, sizeof(visited));
109 }
110
111 void LGraph_insert(ENode ** head, int ivex)
112 {
113 ENode *pnew, *p1, *p2;
114 pnew = (ENode *)malloc(sizeof(ENode));
115 pnew->ivex = ivex;
116 if ( *head == NULL )
117 {
118 *head = pnew;
119
120 pnew->next = NULL;
121 }
122 else
123 {
124 if ( (*head)->ivex > ivex ) //沒頭結點的麻煩
125 {
126 pnew->next = *head;
127 *head = pnew;
128 }
129 else
130 {
131 for (p1 = *head, p2 = p1->next; p2 != NULL ; p1 = p2, p2 = p1->next )
132 {
133 if ( p2->ivex > ivex )
134 break;
135 }
136 pnew->next = p2;
137 p1->next = pnew;
138 }
139 }
140 }
141
142 void DFS(LGraph * G, int vex)
143 {
144 if (TAG == false)
145 {
146 TAG = true;
147 printf("{ ");
148 }
149 printf("%d ", vex);
150 visited[vex] = true;
151 ENode * temp = G->vexs[vex].first_edge;
152 while( temp != NULL )
153 {
154 if (visited[temp->ivex] == false)
155 {
156 DFS(G, temp->ivex);
157 }
158 temp = temp->next;
159 }
160 }
161 void BFS(LGraph * G, int vex)
162 {
163 Queue Q = CreateQueue(G->vexnum);
164 if (TAG == false)
165 {
166 TAG = true;
167 printf("{ ");
168 }
169 printf("%d ", vex);
170 visited[vex] = true;
171 AddQ(Q, vex);
172 while (!IsEmpty(Q))
173 {
174 vex = DeleteQ(Q);
175 ENode * temp = G->vexs[vex].first_edge;
176 while (temp != NULL)
177 {
178 if ( visited[temp->ivex] == false )
179 {
180 printf("%d ",temp->ivex);
181 visited[temp->ivex] = true;
182 AddQ(Q, temp->ivex);
183 }
184 temp = temp->next;
185 }
186 }
187 free(Q->Data);
188 free(Q);
189 }
190
191
192 //隊列基本操作
193 Queue CreateQueue( int MaxSize )
194 {
195 Queue Q = (Queue)malloc(sizeof(struct QNode));
196 Q->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
197 Q->Front = Q->Rear = 0;
198 Q->MaxSize = MaxSize;
199 return Q;
200 }
201
202 bool IsFull( Queue Q )
203 {
204 return ((Q->Rear+1)%Q->MaxSize == Q->Front);
205 }
206
207 bool AddQ( Queue Q, ElementType X )
208 {
209 if ( IsFull(Q) ) {
210 printf("隊列滿");
211 return false;
212 }
213 else {
214 Q->Rear = (Q->Rear+1)%Q->MaxSize;
215 Q->Data[Q->Rear] = X;
216 return true;
217 }
218 }
219
220 bool IsEmpty( Queue Q )
221 {
222 return (Q->Front == Q->Rear);
223 }
224
225 ElementType DeleteQ( Queue Q )
226 {
227 if ( IsEmpty(Q) ) {
228 printf("隊列空");
229 return 0;
230 }
231 else {
232 Q->Front =(Q->Front+1)%Q->MaxSize;
233 return Q->Data[Q->Front];
234 }
235 }
View Code
