生成一个用广度优先算法求解连通图的代码

以下是用Python编写的广度优先算法求解连通图的代码：

from collections import deque

# 定义图的邻接表表示
graph = {
    1: [2, 3],
    2: [1, 3, 4, 5],
    3: [1, 2, 5],
    4: [2, 5],
    5: [2, 3, 4]
}

# 广度优先搜索算法
def bfs(graph, start):
    visited = set()  # 用集合记录已经访问过的节点
    queue = deque([start])  # 用双端队列保存还未访问的节点

    while queue:
        node = queue.popleft()  # 取出队列的左侧节点
        if node not in visited:
            visited.add(node)
            print(node, end=' ')
            queue.extend(graph[node])  # 将当前节点的邻居添加到队列右侧

# 测试代码
bfs(graph, 1)

运行该代码，输出结果为：

1 2 3 4 5

该代码通过邻接表表示图的形式，使用双端队列保存还未访问的节点，使用集合记录已经访问过的节点，实现了广度优先搜索算法。

相关问题

生成一个用广度优先算法求解连通图的c语言代码

以下是用广度优先搜索算法实现连通图的C语言代码：

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

#define MAX_VERTEX_NUM 100    // 最大顶点数
#define MAX_QUEUE_SIZE 100    // 最大队列长度

/* 队列结构体 */
typedef struct {
    int data[MAX_QUEUE_SIZE];   // 存放队列元素的数组
    int front;                  // 队首指针
    int rear;                   // 队尾指针
} Queue;

/* 图的结构体 */
typedef struct {
    int vertex[MAX_VERTEX_NUM]; // 存放顶点的数组
    int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存放边的二维数组
    int vertex_num;             // 顶点数
    int edge_num;               // 边数
} Graph;

/* 初始化队列 */
void initQueue(Queue *queue) {
    queue->front = queue->rear = 0;
}

/* 判断队列是否为空 */
int isQueueEmpty(Queue *queue) {
    return queue->front == queue->rear;
}

/* 判断队列是否已满 */
int isQueueFull(Queue *queue) {
    return (queue->rear + 1) % MAX_QUEUE_SIZE == queue->front;
}

/* 入队操作 */
void enqueue(Queue *queue, int vertex) {
    if (!isQueueFull(queue)) {
        queue->data[queue->rear] = vertex;
        queue->rear = (queue->rear + 1) % MAX_QUEUE_SIZE;
    }
}

/* 出队操作 */
int dequeue(Queue *queue) {
    int vertex = -1;
    if (!isQueueEmpty(queue)) {
        vertex = queue->data[queue->front];
        queue->front = (queue->front + 1) % MAX_QUEUE_SIZE;
    }
    return vertex;
}

/* 初始化图 */
void initGraph(Graph *graph) {
    int i, j;
    printf("请输入顶点数和边数：\n");
    scanf("%d %d", &graph->vertex_num, &graph->edge_num);
    printf("请输入顶点：\n");
    for (i = 0; i < graph->vertex_num; i++) {
        scanf("%d", &graph->vertex[i]);
    }
    for (i = 0; i < graph->vertex_num; i++) {
        for (j = 0; j < graph->vertex_num; j++) {
            graph->edge[i][j] = 0;
        }
    }
    printf("请输入边的两个顶点：\n");
    for (i = 0; i < graph->edge_num; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        graph->edge[a][b] = graph->edge[b][a] = 1;
    }
}

/* 广度优先搜索 */
void bfs(Graph *graph, int start) {
    int i, vertex;
    int visited[MAX_VERTEX_NUM] = { 0 }; // 标记顶点是否被访问过
    Queue queue;
    initQueue(&queue);  // 初始化队列
    visited[start] = 1; // 标记起始顶点为已访问
    enqueue(&queue, start); // 将起始顶点入队
    printf("广度优先搜索结果：\n");
    while (!isQueueEmpty(&queue)) {
        vertex = dequeue(&queue); // 出队一个顶点
        printf("%d ", graph->vertex[vertex]); // 访问该顶点
        for (i = 0; i < graph->vertex_num; i++) { // 遍历该顶点的邻接顶点
            if (graph->edge[vertex][i] == 1 && visited[i] == 0) { // 如果邻接顶点未被访问过
                visited[i] = 1; // 标记邻接顶点为已访问
                enqueue(&queue, i); // 将邻接顶点入队
            }
        }
    }
}

int main() {
    Graph graph;
    initGraph(&graph); // 初始化图
    bfs(&graph, 0);    // 从第一个顶点开始进行广度优先搜索
    return 0;
}

深度优先求图的连通分量伪代码

深度优先搜索（DFS）是一种用于图的遍历算法，可以用来求解图的连通分量。下面是深度优先搜索求图的连通分量的伪代码：

1. 初始化一个空的集合或数组visited，用于记录已经访问过的节点。
2. 初始化一个空的集合或数组components，用于存储连通分量。
3. 对于图中的每个节点v：
- 如果v没有被访问过，则进行以下步骤：
- 创建一个新的空集合或数组currentComponent，用于存储当前连通分量。
- 调用DFS(v, currentComponent)进行深度优先搜索。
- 将currentComponent添加到components中。
4. 返回components作为结果。

DFS(v, currentComponent)的伪代码如下：

1. 将节点v标记为已访问。
2. 将v添加到currentComponent中。
3. 对于v的每个邻居节点u：
- 如果u没有被访问过，则进行以下步骤：
- 调用DFS(u, currentComponent)进行递归的深度优先搜索。