图遍历的演示

很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示在连通的无向图上访问全部结点的操作。

基本要求

以邻接多重表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。

实现提示

设图的结点不超过30个，每个结点用一个编号表示(如果一个图有n个结点，则它们的编号分别为1，2，…，n)。通过输入图的全部边(存于数据文件中，从文件读写)输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制。注意，生成树的边是有向边，端点顺序不能颠倒。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <stdbool.h>
#include <stdio.h>
#include <string>

// 图的节点结构
struct Node {
    int id;
    struct Node** neighbors;
    int numNeighbors;
    bool visited;
};

// 创建节点
struct Node* createNode(int id) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->id = id;
    node->neighbors = NULL;
    node->numNeighbors = 0;
    node->visited = false;
    return node;
}

// 添加邻居节点
void addNeighbor(struct Node* node, struct Node* neighbor) {
    node->numNeighbors++;
    node->neighbors = (struct Node**)realloc(node->neighbors, node->numNeighbors * sizeof(struct Node*));
    node->neighbors[node->numNeighbors - 1] = neighbor;
}

// 深度优先搜索函数
void dfs(struct Node* node) {
    // 标记当前节点为已访问
    node->visited = true;
    printf("访问的节点： %d\n", node->id);
    // 遍历当前节点的邻居节点
    for (int i = 0; i < node->numNeighbors; i++) {
        struct Node* neighbor = node->neighbors[i];
        if (!neighbor->visited) {
            dfs(neighbor);
        }
    }
}

// 主函数
int main() {
    // 创建节点
    struct Node* node1 = createNode(1);
    struct Node* node2 = createNode(2);
    struct Node* node3 = createNode(3);
    struct Node* node4 = createNode(4);
    struct Node* node5 = createNode(5);
    // 添加节点之间的边
    addNeighbor(node1, node2);
    addNeighbor(node1, node3);
    addNeighbor(node2, node4);
    addNeighbor(node3, node4);
    addNeighbor(node4, node5);
    // 从起始节点开始进行深度优先搜索
    dfs(node1);

    return 0;
}

1
2
3
4
5
访问的节点： 1
访问的节点： 2
访问的节点： 4
访问的节点： 5
访问的节点： 3