一、实验内容 如下图所示，完成如下题目： 1、画出图的邻接矩阵； 2、画出图的邻接表表示图； 3、根据画出的邻接表，以顶点0位开始，写出图的深度优先遍历序列广度优先遍历序列。

首先，让我解释一下术语。"邻接矩阵"是一种图数据结构，它是一个二维数组，其中行代表源节点，列表示目标节点，值为1或0（通常非零表示连接）。"邻接表"则是链式存储每个节点的邻接节点，更节省空间，尤其对于稀疏图。

假设我们有一个简单的无向图，如下面所示：

   0 --- 1
   |     |
   |     v
   2 --- 3

1. **邻接矩阵**:
对于这个图，邻接矩阵会是这样的：

   | 0 | 1 | 2 | 3 |
   --------------------------------
   0 | 0 | 1 | 0 | 0 |
   1 | 1 | 0 | 1 | 0 |
   2 | 0 | 1 | 0 | 1 |
   3 | 0 | 0 | 1 | 0 |

2. **邻接表**:

   0: [1]
   1: [0, 2]
   2: [0, 3]
   3: [1]

每个节点旁边列出了与其相连的节点编号。

3. **深度优先遍历（DFS）**从顶点0出发，顺序可能是：0 -> 1 -> 2 -> 3 或 0 -> 1 -> 3。
**广度优先遍历（BFS）**从顶点0出发，顺序可能是：0 -> 1 -> 3 -> 2。

相关问题

图的遍历操作是从图的某一顶点出发，依次访问图中其余顶点，且每个顶点仅被访问一次。请完成无向连通图的深度优先搜索和广度优先搜索。 输入 输入数据为多组，每组数据包含多行，第一行为2个整数n（1<=n<=30）,e，n为图的顶点数，e为边数，接下来是e行，每行2个整数，是一个顶点对，代表一条边所依附的两个顶点。例如，下图的输入数据为： 5 6 1 2 1 3 2 4 3 4 2 5 4 5 输出 每个图的深度优先搜索和广度优先搜索序列，每个序列占一行，输出的每个顶点后有一个空格。 样例输入 3 3 1 2 1 3 2 3 5 6 1 2 1 3 2 4 3 4 2 5 4 5 样例输出 1 2 3 1 2 3 1 2 4 3 5 1 2 3 4 5 提示 如题目描述中图所示，顶点值为整型，亦可看为顶点序号，取值从1开始。图中顶点数不超过30个，遍历时由顶点值最小的顶点开始。C语言代码

以下是C语言实现无向连通图的深度优先搜索和广度优先搜索的示例代码：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAXN 30

int adj[MAXN + 1][MAXN + 1]; // 邻接矩阵
bool visited[MAXN + 1]; // 标记顶点是否被访问过

// 深度优先搜索
void dfs(int v, int n) {
    visited[v] = true; // 标记当前顶点已被访问
    printf("%d ", v); // 输出当前顶点
    for (int i = 1; i <= n; i++) {
        if (adj[v][i] && !visited[i]) { // 如果顶点v和i有连接且i未被访问
            dfs(i, n); // 递归访问顶点i
        }
    }
}

// 广度优先搜索
void bfs(int v, int n) {
    int queue[MAXN + 1]; // 定义队列
    int head = 0, tail = 0;
    visited[v] = true; // 标记当前顶点已被访问
    printf("%d ", v); // 输出当前顶点
    queue[tail++] = v; // 将当前顶点入队
    while (head < tail) {
        int u = queue[head++]; // 从队列头部取出一个顶点
        for (int i = 1; i <= n; i++) {
            if (adj[u][i] && !visited[i]) { // 如果顶点u和i有连接且i未被访问
                visited[i] = true; // 标记当前顶点已被访问
                printf("%d ", i); // 输出当前顶点
                queue[tail++] = i; // 将当前顶点入队
            }
        }
    }
}

int main() {
    int n, e;
    while (scanf("%d%d", &n, &e) == 2) {
        // 初始化邻接矩阵和visited数组
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                adj[i][j] = 0;
            }
            visited[i] = false;
        }
        // 读入边信息，构造邻接矩阵
        for (int i = 1; i <= e; i++) {
            int a, b;
            scanf("%d%d", &a, &b);
            adj[a][b] = adj[b][a] = 1;
        }
        // 深度优先搜索
        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                dfs(i, n);
            }
        }
        printf("\n");
        // 重新初始化visited数组
        for (int i = 1; i <= n; i++) {
            visited[i] = false;
        }
        // 广度优先搜索
        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                bfs(i, n);
            }
        }
        printf("\n");
    }
    return 0;
}

在以上示例代码中，我们使用邻接矩阵来表示无向图。首先读入边信息，构造邻接矩阵。然后分别使用深度优先搜索和广度优先搜索遍历无向图，输出遍历结果。

在深度优先搜索中，我们从顶点值最小的顶点开始递归搜索。在搜索过程中，标记已经访问过的顶点，避免重复访问。对于当前顶点v，遍历所有与它有连接的顶点i，如果i未被访问过，则递归访问顶点i。

在广度优先搜索中，我们使用队列来存储已经访问过但未被处理的顶点。从顶点值最小的顶点开始，将它入队，然后不断从队列头部取出一个顶点u，并遍历所有与它有连接的顶点i，如果i未被访问过，则输出顶点i并将它入队。

需要注意的是，在每次遍历之前，需要重新初始化visited数组，避免上次遍历的影响。