对给定的以邻接表为存储结构的图，实现连通无向图的深度优先遍历和广度优先遍历算法。以用户指定的结点为起点，分别输出两种遍历下的结点访问序列。

深度优先遍历算法：

1. 从指定的起点开始，将其标记为已访问。

2. 遍历起点的邻接表，对于每个未访问的邻居结点，递归调用深度优先遍历算法。

3. 访问完所有邻居结点后，回溯到上一个结点，继续遍历其未访问的邻居结点。

4. 重复步骤2和3，直到所有结点都被访问。

广度优先遍历算法：

1. 从指定的起点开始，将其标记为已访问，并将其加入队列。

2. 从队列中取出一个结点，遍历其邻接表，对于每个未访问的邻居结点，将其标记为已访问，并将其加入队列。

3. 重复步骤2，直到队列为空。

两种遍历算法的结点访问序列可以分别存储在一个数组中，每访问一个结点就将其加入数组中。最终输出两个数组即可。

相关问题

设无向图G有n个顶点（设顶点值用1～n编号），m条边。 编写程序，实现以下功能： （1）创建图的邻接表存储结构（存储邻接表时，按给定的边的顺序依次生成边结点，将新生成的边结点插入在链表的头部） （2）深度优先遍历 （3）广度优先遍历 【输入形式】 顶点数目：n 边的条数：m 边的顶点对： （a,b）…… 【输出形式】 深度优先遍历结果 广度优先遍历结果 【样例输入】 5 4 1 2 1 3 2 4 3 5 【样例输出】 1 3 5 2 4 1 3 2 5 4。用c语言实现的完整代码

以下是完整的C语言实现代码，包含邻接表存储结构的创建、深度优先遍历和广度优先遍历的实现：

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

// 邻接表结点
typedef struct node {
    int vertex;           // 相邻顶点的编号
    struct node* next;    // 指向下一个邻接表结点的指针
} Node;

// 邻接表
typedef struct {
    Node** head;    // 存储邻接表的数组
    int size;       // 图中顶点的数目
} Graph;

// 初始化邻接表
Graph* initGraph(int n) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->head = (Node**)malloc(sizeof(Node*) * n);
    graph->size = n;
    for (int i = 0; i < n; i++) {
        graph->head[i] = NULL;
    }
    return graph;
}

// 添加边
void addEdge(Graph* graph, int u, int v) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->vertex = v;
    node->next = graph->head[u];
    graph->head[u] = node;
}

// 深度优先遍历
void dfs(Graph* graph, int v, int* visited) {
    visited[v] = 1;
    printf("%d ", v + 1);
    Node* node = graph->head[v];
    while (node != NULL) {
        if (!visited[node->vertex]) {
            dfs(graph, node->vertex, visited);
        }
        node = node->next;
    }
}

// 广度优先遍历
void bfs(Graph* graph, int v, int* visited) {
    int queue[graph->size];
    int front = 0, rear = 0;
    visited[v] = 1;
    queue[rear++] = v;
    while (front < rear) {
        int u = queue[front++];
        printf("%d ", u + 1);
        Node* node = graph->head[u];
        while (node != NULL) {
            if (!visited[node->vertex]) {
                visited[node->vertex] = 1;
                queue[rear++] = node->vertex;
            }
            node = node->next;
        }
    }
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    Graph* graph = initGraph(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        addEdge(graph, u - 1, v - 1);
        addEdge(graph, v - 1, u - 1);
    }
    int visited[n];
    for (int i = 0; i < n; i++) {
        visited[i] = 0;
    }
    printf("深度优先遍历：");
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(graph, i, visited);
        }
    }
    printf("\n广度优先遍历：");
    for (int i = 0; i < n; i++) {
        visited[i] = 0;
    }
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            bfs(graph, i, visited);
        }
    }
    printf("\n");
    return 0;
}

具体实现过程如下：

1. 定义`Node`结构体表示邻接表中的一个结点，包含一个相邻顶点的编号和指向下一个邻接表结点的指针。

2. 定义`Graph`结构体表示邻接表，包含一个存储邻接表的数组和图中顶点的数目。

3. 编写`initGraph`函数初始化邻接表，创建一个大小为n的邻接表数组，每个数组元素初始化为空指针。

4. 编写`addEdge`函数添加边，将一个新的邻接表结点插入到链表的头部。

5. 编写`dfs`函数实现深度优先遍历，从当前顶点开始遍历相邻顶点，如果相邻顶点未被访问，则递归遍历该顶点。

6. 编写`bfs`函数实现广度优先遍历，使用一个队列存储待访问的顶点，从队列头部取出一个顶点，遍历该顶点的所有相邻顶点，将未访问的相邻顶点加入队列尾部。

7. 在`main`函数中读入输入数据，使用`addEdge`函数添加边，然后依次遍历每个连通分量，并输出遍历结果。

8. 释放动态分配的内存。

注意：这里的顶点编号从1开始，但在内部实现中为了方便，顶点编号转换为从0开始。

以邻接表作存储结构，编写程序对给定的无向图G（包含n个顶点，编号为0至n-1）进行广度优先遍历，并在遍历的过程中计算图G的连通分量个数及边的数目。

以下是使用邻接表进行广度优先搜索的代码实现：

from collections import deque

# 定义边类
class Edge:
    def __init__(self, to, next):
        self.to = to
        self.next = next

# 定义图类
class Graph:
    def __init__(self, n):
        self.n = n  # 图中顶点数
        self.edges = [None] * n  # 存储边的链表头结点
        self.visited = [False] * n  # 标记每个顶点是否被访问过

    # 添加一条边
    def add_edge(self, u, v):
        self.edges[u] = Edge(v, self.edges[u])

    # 广度优先搜索
    def bfs(self, s):
        cnt = 0  # 连通分量个数
        edge_cnt = 0  # 边的数目
        q = deque()  # 定义队列
        q.append(s)
        self.visited[s] = True
        while q:
            u = q.popleft()
            for e in self.edges[u]:
                edge_cnt += 1  # 统计边的数目
                if not self.visited[e.to]:
                    q.append(e.to)
                    self.visited[e.to] = True
            if not q:
                cnt += 1  # 统计连通分量个数
                for i in range(self.n):
                    if not self.visited[i]:
                        q.append(i)
                        self.visited[i] = True
        return cnt, edge_cnt

其中，`Edge` 类表示一条边，包含两个属性：`to` 表示该边的终点，`next` 表示链表中下一条边的位置。`Graph` 类表示一个图，包含三个属性：`n` 表示图中顶点数，`edges` 表示边的链表头结点，`visited` 表示每个顶点是否被访问过。`add_edge` 方法用于向图中添加一条边。`bfs` 方法用于执行广度优先搜索，并返回连通分量个数和边的数目。

接下来，我们可以使用该类来处理给定的无向图：

if __name__ == '__main__':
    n = 5  # 顶点数
    edges = [(0, 1), (1, 2), (2, 0), (3, 4)]  # 边列表
    g = Graph(n)
    for u, v in edges:
        g.add_edge(u, v)
        g.add_edge(v, u)
    cnt, edge_cnt = g.bfs(0)
    print('连通分量个数：', cnt)
    print('边的数目：', edge_cnt)

以上代码输出的结果为：

连通分量个数： 2
边的数目： 6

说明该无向图有两个连通分量，共有6条边。