【PTA数据结构 | C语言版】列出连通集

本专栏持续输出数据结构题目集，欢迎订阅。

题目

给定一个有 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 10

typedef 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;
        }
    }
}