无向图的bfs算法举例

下面是一个无向图 BFS 算法的示例：

假设有如下无向图：

1 -- 2 -- 3
|    |    |
4 -- 5 -- 6

我们可以通过 BFS 算法遍历这个无向图，得到遍历的次序。假设我们从节点 1 开始遍历，那么遍历过程如下：

1. 将节点 1 加入队列中，并标记为已访问。
2. 从队列中取出节点 1，并遍历其所有相邻节点，即节点 2 和节点 4，将这些节点加入队列中，并标记为已访问。
3. 从队列中取出节点 2，并遍历其所有相邻节点，即节点 1、3 和 5。由于节点 1 已经被访问过，因此不将其加入队列中。将节点 3 和节点 5 加入队列中，并标记为已访问。
4. 从队列中取出节点 4，并遍历其所有相邻节点，即节点 1 和节点 5。由于节点 1 已经被访问过，因此不将其加入队列中。将节点 5 加入队列中，并标记为已访问。
5. 从队列中取出节点 3，并遍历其所有相邻节点，即节点 2 和节点 6。由于节点 2 已经被访问过，因此不将其加入队列中。将节点 6 加入队列中，并标记为已访问。
6. 从队列中取出节点 5，并遍历其所有相邻节点，即节点 2、4 和节点 6。由于节点 2 和节点 4 已经被访问过，因此不将其加入队列中。将节点 6 加入队列中，并标记为已访问。
7. 从队列中取出节点 6，并遍历其所有相邻节点，即节点 3 和节点 5。由于这些节点都已经被访问过，不需要将其加入队列中。
8. 重复以上步骤，直到队列为空。

综上，通过 BFS 算法遍历无向图可以得到遍历的次序，但无法得到特殊的排序次序。

相关问题

bfs算法有向图c语言

以下是BFS算法在C语言中的有向图实现：

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

#define MAX 100

// 队列结构体
struct Queue {
    int items[MAX];
    int front;
    int rear;
};

// 创建队列
struct Queue* createQueue() {
    struct Queue* q = malloc(sizeof(struct Queue));
    q->front = -1;
    q->rear = -1;
    return q;
}

// 判断队列是否为空
int isEmpty(struct Queue* q) {
    if(q->rear == -1) 
        return 1;
    else 
        return 0;
}

// 入队
void enqueue(struct Queue* q, int value) {
    if(q->rear == MAX-1)
        printf("队列已满！\n");
    else {
        if(q->front == -1)
            q->front = 0;
        q->rear++;
        q->items[q->rear] = value;
    }
}

// 出队
int dequeue(struct Queue* q) {
    int item;
    if(isEmpty(q)) {
        printf("队列为空！\n");
        item = -1;
    }
    else {
        item = q->items[q->front];
        q->front++;
        if(q->front > q->rear) {
            q->front = q->rear = -1;
        }
    }
    return item;
}

// 初始化图
void initGraph(int graph[][MAX], int n) {
    int i, j;
    for(i=0; i<n; i++) {
        for(j=0; j<n; j++) {
            graph[i][j] = 0;
        }
    }
}

// 添加边
void addEdge(int graph[][MAX], int u, int v) {
    graph[u][v] = 1;
}

// BFS算法
void bfs(int graph[][MAX], int start, int n) {
    // 初始化visited数组
    int visited[MAX] = {0};

    // 创建队列
    struct Queue* q = createQueue();

    // 标记起点为已访问并入队
    visited[start] = 1;
    enqueue(q, start);

    // 输出遍历结果
    printf("BFS遍历结果: ");
    while(!isEmpty(q)) {
        int currentNode = dequeue(q);
        printf("%d ", currentNode);

        // 遍历当前节点的邻居节点
        int i;
        for(i=0; i<n; i++) {
            if(graph[currentNode][i] == 1 && visited[i] == 0) {
                visited[i] = 1;
                enqueue(q, i);
            }
        }
    }
}

int main() {
    int n; // 顶点数
    int graph[MAX][MAX]; // 邻接矩阵

    // 初始化图
    printf("请输入顶点数：");
    scanf("%d", &n);
    initGraph(graph, n);

    // 添加边
    int u, v;
    printf("请输入边（-1结束）：\n");
    while(1) {
        scanf("%d%d", &u, &v);
        if(u == -1 || v == -1) {
            break;
        }
        else {
            addEdge(graph, u, v);
        }
    }

    // BFS遍历
    int start;
    printf("请输入起点：");
    scanf("%d", &start);
    bfs(graph, start, n);

    return 0;
}

以上代码中，`graph`数组为邻接矩阵，`createQueue()`函数用于创建队列，`enqueue()`函数用于入队，`dequeue()`函数用于出队，`initGraph()`函数用于初始化图，`addEdge()`函数用于添加边，`bfs()`函数为BFS算法实现。

能不能写一个无向图的BFS算法

当然可以，以下是一个无向图的BFS算法的示例代码：

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

void bfs(vector<vector<int>>& graph, int start) {
    queue<int> q;
    vector<bool> visited(graph.size(), false);
    q.push(start);
    visited[start] = true;
    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        cout << curr << " ";
        for (int neighbor : graph[curr]) {
            if (!visited[neighbor]) {
                q.push(neighbor);
                visited[neighbor] = true;
            }
        }
    }
}

int main() {
    vector<vector<int>> graph = {{1, 2}, {0, 2, 3}, {0, 1, 3}, {1, 2}};
    bfs(graph, 0);
    return 0;
}

这个算法使用了一个队列和一个visited数组来实现BFS。我们从起点开始，将其加入队列中，并将其标记为已访问。然后，我们不断从队列中取出一个节点，并将其未访问的邻居加入队列中，并标记为已访问。这样，我们就可以遍历整个图了。