图的广度优先遍历具体代码

以下是图的广度优先遍历的具体代码：

void BFS(int s) {
    queue<int> q;
    q.push(s);
    visited[s] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

这段代码使用了队列来实现图的广度优先遍历，从起点开始，将其加入队列中，然后依次取出队列中的元素，遍历其所有邻居节点，将未访问过的邻居节点加入队列中，并标记为已访问。重复以上步骤，直到队列为空。

相关问题

深度优先遍历 广度优先遍历的代码示例

下面是深度优先遍历和广度优先遍历的代码示例（以无向图为例）：

深度优先遍历的代码示例：

def dfs(graph, start, visited):
    visited.add(start)
    print(start, end=' ')

    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

# 以邻接表表示图
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

visited = set()
dfs(graph, 'A', visited)

广度优先遍历的代码示例：

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        vertex = queue.popleft()
        print(vertex, end=' ')

        for neighbor in graph[vertex]:
            if neighbor not in visited:
                queue.append(neighbor)
                visited.add(neighbor)

# 以邻接表表示图
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

bfs(graph, 'A')

以上代码示例中，深度优先遍历和广度优先遍历都使用了图的邻接表表示。在深度优先遍历中，使用递归方式实现，通过记录已访问的节点来避免重复访问。在广度优先遍历中，使用队列来存储待访问的节点，并通过记录已访问的节点来避免重复访问。

图的广度优先遍历算法代码

图的广度优先遍历（Breadth-First Search, BFS）是一种用于遍历或搜索树和图数据结构的算法。它从根节点开始，按照层级顺序逐层遍历，直到找到目标节点或者遍历完整个图。以下是使用Python实现图的BFS算法的一个基本示例，假设我们有一个邻接列表表示的图：

from collections import deque

def bfs(graph, start):
    visited = set()  # 用来记录已访问过的节点
    queue = deque([start])  # 使用双端队列作为广度优先搜索的数据结构
    while queue:  # 只要队列不为空，就继续遍历
        vertex = queue.popleft()  # 取出队首元素
        if vertex not in visited:
            visited.add(vertex)  # 标记为已访问
            print(vertex, end=" ")  # 输出节点
            # 添加当前节点的所有邻居到队列
            for neighbor in graph[vertex]:
                queue.append(neighbor)

# 示例图：邻接列表表示
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

bfs(graph, 'A')  # 从节点A开始进行BFS

在上面的代码中，`graph`是一个字典，键是节点，值是其邻居列表。`start`是起点。算法会按照BFS的方式打印出从`start`到其他所有节点的路径。