图上的广度优先遍历-邻接矩阵存图

广度优先遍历是一种用于图的遍历的算法。在邻接矩阵存储图中，广度优先遍历通过逐层访问图中的顶点，先访问与起始顶点直接相邻的顶点，然后再访问与这些顶点直接相邻的顶点，以此类推，直到遍历完所有可达的顶点。具体实现广度优先遍历的算法如下：

1. 创建一个大小为顶点数的布尔类型的数组visited，用于标记顶点是否已被访问。
2. 创建一个队列queue，用于存储待访问的顶点。
3. 将起始顶点i标记为已访问，并将其入队。
4. 当队列不为空时，执行以下步骤：
- 出队一个顶点v，并输出该顶点。
- 遍历与顶点v直接相邻的顶点w，若顶点w未被访问，则将其标记为已访问，并将其入队。
5. 重复步骤4直到队列为空。

以上就是邻接矩阵存图上的广度优先遍历算法的具体步骤。

相关问题

图的广度优先遍历基于邻接矩阵 python实现

以下是基于邻接矩阵的图的广度优先遍历的 Python 实现：

from queue import Queue

# 定义邻接矩阵
graph = [[0, 1, 1, 0],
         [1, 0, 1, 1],
         [1, 1, 0, 1],
         [0, 1, 1, 0]]

# 定义起始节点
start_node = 0

# 定义 BFS 函数
def bfs(graph, start):
    # 创建一个队列并将起始节点入队
    queue = Queue()
    queue.put(start)
    
    # 定义 visited 数组记录已经访问过的节点
    visited = [False] * len(graph)
    visited[start] = True
    
    # 从队列中取出元素，并访问其邻居节点
    while not queue.empty():
        node = queue.get()
        print(node)
        for neighbor in range(len(graph[node])):
            if graph[node][neighbor] == 1 and not visited[neighbor]:
                queue.put(neighbor)
                visited[neighbor] = True

# 调用 BFS 函数
bfs(graph, start_node)

运行结果：

0
1
2
3

这里的邻接矩阵 `graph` 表示有 4 个节点的无向图，其中 `graph[i][j]` 表示节点 i 和节点 j 之间是否有边。前面的 BFS 函数基于队列实现，每次取出队列头的元素，并访问它的邻居节点，直到队列为空。为了避免重复访问同一个节点，我们使用 `visited` 数组记录已经访问过的节点。

广度优先遍历（邻接矩阵BFS）c++实现

以下是邻接矩阵BFS的C++实现：

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

const int MAXN = 100; // 最大顶点数
int G[MAXN][MAXN]; // 邻接矩阵
bool vis[MAXN]; // 标记数组

void BFS(int s, int n) { // s为起点，n为顶点数
    queue<int> q;
    q.push(s);
    vis[s] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cout << u << " ";
        for (int v = 0; v < n; v++) {
            if (G[u][v] && !vis[v]) {
                q.push(v);
                vis[v] = true;
            }
        }
    }
}

int main() {
    int n, m; // n为顶点数，m为边数
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        G[u][v] = G[v][u] = 1; // 无向图
    }
    BFS(0, n);
    return 0;
}