本專欄持續輸出數據結構題目集，歡迎訂閱。

題目

給定一個有 n 個頂點和 m 條邊的無向圖，請用深度優先遍歷（DFS）和廣度優先遍歷（BFS）分別列出其所有的連通集。假設頂點從 0 到 n?1 編號。進行搜索時，假設我們總是從編號最小的頂點出發，按編號遞增的順序訪問鄰接點。

輸入格式:
輸入第 1 行給出 2 個整數 n (0<n≤10) 和 m，分別是圖的頂點數和邊數。隨后 m 行，每行給出一條邊的兩個端點。每行中的數字之間用 1 空格分隔。

輸出格式:
按照"{ v1 v2 … vk}"的格式，每行輸出一個連通集。先輸出 DFS 的結果，再輸出 BFS 的結果。

輸入樣例:
8 6
0 7
0 1
2 0
4 1
2 4
3 5

輸出樣例:
{ 0 1 4 2 7 }
{ 3 5 }
{ 6 }
{ 0 1 2 7 4 }
{ 3 5 }
{ 6 }

代碼

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAX_VERTEX 10typedef struct Node {int vertex;struct Node* next;
} Node;typedef struct {Node* adj[MAX_VERTEX];int n;
} Graph;typedef struct {int data[MAX_VERTEX];int top;
} Stack;typedef struct {int data[MAX_VERTEX];int front, rear;
} Queue;// 函數聲明
void initGraph(Graph* g, int n);
void addEdge(Graph* g, int src, int dest);
void DFS(Graph* g, int v, int visited[], int component[], int* count);
void BFS(Graph* g, int v, int visited[], int component[], int* count);
void initQueue(Queue* q);
int isQueueEmpty(Queue* q);
void enqueue(Queue* q, int v);
int dequeue(Queue* q);
void initStack(Stack* s);
int isStackEmpty(Stack* s);
void push(Stack* s, int v);
int pop(Stack* s);
int peek(Stack* s);int main() {int n, m;scanf("%d %d", &n, &m);Graph g;initGraph(&g, n);for (int i = 0; i < m; i++) {int src, dest;scanf("%d %d", &src, &dest);addEdge(&g, src, dest);}// DFS遍歷int visited[MAX_VERTEX] = {0};for (int i = 0; i < n; i++) {if (!visited[i]) {int component[MAX_VERTEX];int count = 0;DFS(&g, i, visited, component, &count);printf("{");for (int j = 0; j < count; j++) {printf(" %d", component[j]);}printf(" }\n");}}// BFS遍歷memset(visited, 0, sizeof(visited));for (int i = 0; i < n; i++) {if (!visited[i]) {int component[MAX_VERTEX];int count = 0;BFS(&g, i, visited, component, &count);printf("{");for (int j = 0; j < count; j++) {printf(" %d", component[j]);}printf(" }\n");}}return 0;
}// 初始化圖
void initGraph(Graph* g, int n) {g->n = n;for (int i = 0; i < n; i++) {g->adj[i] = NULL;}
}// 添加無向邊（按編號遞增順序插入）
void addEdge(Graph* g, int src, int dest) {// 添加src->dest的邊（按遞增順序插入）Node* newNode = (Node*)malloc(sizeof(Node));newNode->vertex = dest;Node* prev = NULL;Node* curr = g->adj[src];while (curr != NULL && curr->vertex < dest) {prev = curr;curr = curr->next;}if (prev == NULL) {newNode->next = g->adj[src];g->adj[src] = newNode;} else {newNode->next = curr;prev->next = newNode;}// 添加dest->src的邊（按遞增順序插入）newNode = (Node*)malloc(sizeof(Node));newNode->vertex = src;prev = NULL;curr = g->adj[dest];while (curr != NULL && curr->vertex < src) {prev = curr;curr = curr->next;}if (prev == NULL) {newNode->next = g->adj[dest];g->adj[dest] = newNode;} else {newNode->next = curr;prev->next = newNode;}
}// 初始化棧
void initStack(Stack* s) {s->top = -1;
}// 判斷棧是否為空
int isStackEmpty(Stack* s) {return s->top == -1;
}// 入棧
void push(Stack* s, int v) {s->data[++(s->top)] = v;
}// 出棧
int pop(Stack* s) {return s->data[(s->top)--];
}// 獲取棧頂元素
int peek(Stack* s) {return s->data[s->top];
}// 非遞歸深度優先搜索（避免棧溢出）
void DFS(Graph* g, int v, int visited[], int component[], int* count) {Stack stack;initStack(&stack);push(&stack, v);while (!isStackEmpty(&stack)) {int u = pop(&stack);if (!visited[u]) {visited[u] = 1;component[(*count)++] = u;// 逆序處理鄰接點，確保按編號升序訪問Node* temp = g->adj[u];Node* nodes[MAX_VERTEX];int nodeCount = 0;while (temp != NULL) {nodes[nodeCount++] = temp;temp = temp->next;}for (int i = nodeCount - 1; i >= 0; i--) {int adjVertex = nodes[i]->vertex;if (!visited[adjVertex]) {push(&stack, adjVertex);}}}}
}// 初始化隊列
void initQueue(Queue* q) {q->front = q->rear = 0;
}// 判斷隊列是否為空
int isQueueEmpty(Queue* q) {return q->front == q->rear;
}// 入隊
void enqueue(Queue* q, int v) {q->data[q->rear++] = v;
}// 出隊
int dequeue(Queue* q) {return q->data[q->front++];
}// 廣度優先搜索
void BFS(Graph* g, int v, int visited[], int component[], int* count) {Queue q;initQueue(&q);visited[v] = 1;enqueue(&q, v);component[(*count)++] = v;while (!isQueueEmpty(&q)) {int u = dequeue(&q);Node* temp = g->adj[u];while (temp != NULL) {int adjVertex = temp->vertex;if (!visited[adjVertex]) {visited[adjVertex] = 1;enqueue(&q, adjVertex);component[(*count)++] = adjVertex;}temp = temp->next;}}
}