Python中如何遍历图(Graph)
在Python中，可以使用深度优先搜索(DFS)或广度优先搜索(BFS)的方式遍历图。下面分别给出这两种方式的示例代码。
深度优先搜索：
graph = { # 用邻接表表示图
'pidancode.com': ['google.com', 'facebook.com', 'yahoo.com'],
'google.com': ['bing.com'],
'facebook.com': ['yahoo.com'],
'yahoo.com': ['google.com', 'pidancode.com']
}
visited = set() # 已访问的节点集合
def dfs(node):
visited.add(node) # 将当前节点标记为已访问
print(node) # 处理当前节点
for neighbor in graph.get(node, []):
if neighbor not in visited: # 如果邻居节点未被访问，递归遍历它
dfs(neighbor)
dfs('pidancode.com') # 从起始节点开始遍历
输出结果：
pidancode.com google.com bing.com facebook.com yahoo.com
广度优先搜索：
from collections import deque graph = { # 用邻接表表示图 'pidancode.com': ['google.com', 'facebook.com', 'yahoo.com'], 'google.com': ['bing.com'], 'facebook.com': ['yahoo.com'], 'yahoo.com': ['google.com', 'pidancode.com'] } visited = set() # 已访问的节点集合 def bfs(node): queue = deque([node]) # 使用双端队列存储待处理的节点 visited.add(node) # 将起始节点标记为已访问 while queue: curr_node = queue.popleft() # 从队列头部取出一个节点 print(curr_node) # 处理当前节点 for neighbor in graph.get(curr_node, []): if neighbor not in visited: # 如果邻居节点未被访问，将它加入队列 visited.add(neighbor) queue.append(neighbor) bfs('pidancode.com') # 从起始节点开始遍历
输出结果：
pidancode.com google.com facebook.com yahoo.com bing.com
相关文章