邻接矩阵的广度优先遍历

邻接矩阵的广度优先遍历可以通过队列实现。具体步骤如下：

1. 从起始顶点开始，将其标记为已访问，并将其加入队列中。
2. 从队列中取出第一个顶点，遍历其所有邻接点，将未访问的邻接点标记为已访问，并将其加入队列中。
3. 重复步骤2，直到队列为空。

下面是一个示例代码，假设邻接矩阵为adj_matrix，起始顶点为start_vertex：

def bfs(adj_matrix, start_vertex):
    visited = [False] * len(adj_matrix) # 标记所有顶点是否已访问
    queue = [start_vertex] # 初始化队列
    visited[start_vertex] = True # 标记起始顶点已访问

    while queue:
        vertex = queue.pop(0) # 取出队列中的第一个顶点
        print(vertex, end=' ') # 输出顶点值

        # 遍历邻接点
        for i in range(len(adj_matrix[vertex])):
            if adj_matrix[vertex][i] == 1 and not visited[i]:
                visited[i] = True # 标记邻接点已访问
                queue.append(i) # 将邻接点加入队列

相关问题

邻接矩阵广度优先遍历

邻接矩阵广度优先遍历是一种图的遍历算法，用于遍历图中所有节点。具体步骤如下：

1. 创建一个队列，将起始节点放入队列中。
2. 创建一个visited数组，用于记录每个节点是否被访问过，将起始节点标记为已访问。
3. 当队列不为空时，执行以下操作：
- 从队列中取出一个节点，访问该节点。
- 遍历该节点的所有邻居节点，如果邻居节点未被访问过，则将其标记为已访问，并将其加入队列中。
4. 重复步骤3，直到队列为空。

下面是一个Python实现的邻接矩阵广度优先遍历的例子：

def BFSTraverse(graph, start):
    queue = []  # 创建一个队列
    visited = [False] * len(graph)  # 创建一个visited数组，初始值为False
    queue.append(start)  # 将起始节点放入队列中
    visited[start] = True  # 标记起始节点为已访问

    while queue:
        node = queue.pop(0)  # 从队列中取出一个节点
        print(node, end=' ')  # 访问该节点

        for i in range(len(graph)):
            if graph[node][i] != 0 and not visited[i]:  # 遍历该节点的所有邻居节点
                visited[i] = True  # 标记邻居节点为已访问
                queue.append(i)  # 将邻居节点加入队列中

# 示例代码
graph = [[0, 1, 1, 0],
         [1, 0, 0, 1],
         [1, 0, 0, 1],
         [0, 1, 1, 0]]
BFSTraverse(graph, 0)  # 从节点0开始遍历

邻接矩阵广度优先遍历c语言算法代码

以下是邻接矩阵广度优先遍历的C语言算法代码：

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

#define MAX 100 // 最大顶点数

int arc[MAX][MAX]; // 边表二维数组，对，行列的下标对应实际存在的顶点，值为1表示两顶点间有边
int visited[MAX]; // 访问标志数组，0表示未访问，1表示已访问

// 邻接矩阵广度优先遍历算法
void BFS(int v, int n) {
    int queue[MAX], front = 0, rear = 0; // 队列
    int i, j;
    printf("%d ", v); // 访问初始顶点v并标记为已访问
    visited[v] = 1;
    queue[rear++] = v; // 初始顶点v入队列
    while (front != rear) { // 队列不为空时循环
        i = queue[front++]; // 出队列
        for (j = 0; j < n; j++) {
            if (arc[i][j] == 1 && visited[j] == 0) { // 顶点i与顶点j有边且顶点j未被访问
                printf("%d ", j); // 访问顶点j并标记为已访问
                visited[j] = 1;
                queue[rear++] = j; // 顶点j入队列
            }
        }
    }
}

int main() {
    int n = 5; // 顶点数
    int m = 6; // 边数
    int i, j, v1, v2;
    // 初始化边表
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            arc[i][j] = 0;
        }
    }
    // 建立边表
    for (i = 0; i < m; i++) {
        scanf("%d%d", &v1, &v2);
        arc[v1][v2] = 1;
        arc[v2][v1] = 1;
    }
    // 初始化访问标志数组
    for (i = 0; i < n; i++) {
        visited[i] = 0;
    }
    // 从顶点0开始广度优先遍历
    BFS(0, n);
    return 0;
}