图的广度优先遍历的代码

以下是图的广度优先遍历的代码实现，使用队列来实现：

from collections import deque

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

def bfs(graph, start):
    visited = set()  # 用集合来存储已经访问过的节点
    queue = deque([start])  # 用双端队列来存储待访问的节点
    visited.add(start)
    while queue:
        node = queue.popleft()
        print(node, end=' ')
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# 测试
bfs(graph, 'A')

运行结果为：A B C D E F

相关问题

图的深度优先遍历和广度优先遍历代码

以下是JavaScript实现图的深度优先遍历和广度优先遍历的代码：

深度优先遍历：

function dfs(node) {
  if (!node) return;
  console.log(node.val);
  node.visited = true;
  for (let i = 0; i < node.neighbors.length; i++) {
    const neighbor = node.neighbors[i];
    if (!neighbor.visited) {
      dfs(neighbor);
    }
  }
}

广度优先遍历：

function bfs(node) {
  if (!node) return;
  const queue = [node];
  node.visited = true;
  while (queue.length) {
    const curr = queue.shift();
    console.log(curr.val);
    for (let i = 0; i < curr.neighbors.length; i++) {
      const neighbor = curr.neighbors[i];
      if (!neighbor.visited) {
        neighbor.visited = true;
        queue.push(neighbor);
      }
    }
  }
}

图的深度优先遍历和广度优先遍历代码实现

以下是图的深度优先遍历和广度优先遍历的代码实现，以邻接表形式存储图：

# 图的深度优先遍历
def DFS(graph, start):
    visited = set()  # 记录已经访问过的节点
    stack = [start]  # 用栈来实现深度优先遍历
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            print(node)
            # 将所有未访问的邻居节点入栈，实现深度优先遍历
            stack.extend([n for n in graph[node] if n not in visited])


# 图的广度优先遍历
def BFS(graph, start):
    visited = set()  # 记录已经访问过的节点
    queue = [start]  # 用队列来实现广度优先遍历
    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.add(node)
            print(node)
            # 将所有未访问的邻居节点入队列，实现广度优先遍历
            queue.extend([n for n in graph[node] if n not in visited])

其中，`graph` 表示邻接表形式存储的图，`start` 表示起始节点。在遍历时，用 `visited` 集合记录已经访问过的节点，防止重复访问。在深度优先遍历中，用栈来实现，每次取出栈顶元素并访问，再将其所有未访问的邻居节点入栈。在广度优先遍历中，用队列来实现，每次取出队首元素并访问，再将其所有未访问的邻居节点入队列。