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

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

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` 数组记录已经访问过的节点。

详细解释深度优先和广度优先遍历用邻接矩阵存储的图的代码

深度优先遍历（DFS）和广度优先遍历（BFS）都是图遍历的经典算法，对于邻接矩阵存储的图，它们的主要区别在于遍历的顺序和数据结构的利用。

**深度优先遍历（DFS）邻接矩阵代码示例（C++）**：

#include <vector>
using namespace std;

// 邻接矩阵表示图
vector<vector<int>> adjMatrix;

// 深度优先遍历
void dfs(int start) {
    vector<bool> visited(adjMatrix.size(), false); // 访问标记
    visited[start] = true;
    cout << "Visiting vertex " << start << endl;
    
    for (int i = 0; i < adjMatrix.size(); i++) {
        if (adjMatrix[start][i] && !visited[i]) {
            dfs(i);
        }
    }
}

int main() {
    // 初始化图和起点
    // ...

    cout << "Depth First Traversal:" << endl;
    dfs(startVertex);

    return 0;
}

**广度优先遍历（BFS）邻接矩阵代码示例（C++）**：

#include <queue>
using namespace std;

// 邻接矩阵表示图
vector<vector<int>> adjMatrix;

// 广度优先遍历
void bfs(int start) {
    vector<bool> visited(adjMatrix.size(), false); // 访问标记
    queue<int> q;
    visited[start] = true;
    q.push(start);

    while (!q.empty()) {
        int curr = q.front();
        cout << "Visiting vertex " << curr << endl;
        q.pop();

        for (int i = 0; i < adjMatrix.size(); i++) {
            if (adjMatrix[curr][i] && !visited[i]) {
                visited[i] = true;
                q.push(i);
            }
        }
    }
}

int main() {
    // 初始化图和起点
    // ...

    cout << "Breadth First Traversal:" << endl;
    bfs(startVertex);

    return 0;
}