图的遍历 - 算法入门

← 返回课程算法入门 › 第 8 关

进度 0%

第 8 关：图的遍历

Python/C++进阶

📖 本课目标

本关属于《算法入门》第 8 课。阅读右侧代码模板，理解每一行的作用，然后动手修改并完成练习。

🎯 本课要点

图的遍历

🛠 学习方式

阅读右侧代码模板中的注释与实现
修改代码，尝试达成新的效果
点击「运行」查看实际输出
确认理解后点击「提交」标记本关完成

💡 说明

本关为 Python/C++，浏览器内无法真正执行该语言。当前「运行」输出为演示结果，请在本地环境中编译运行以验证代码。

main.pytest.py

# 图的遍历

from collections import deque

class Graph:
    def __init__(self):
        self.adj = {}
    
    def add_edge(self, u, v):
        if u not in self.adj:
            self.adj[u] = []
        if v not in self.adj:
            self.adj[v] = []
        self.adj[u].append(v)
        self.adj[v].append(u)
    
    def bfs(self, start):
        """广度优先搜索"""
        visited = set()
        queue = deque([start])
        visited.add(start)
        order = []
        
        while queue:
            node = queue.popleft()
            order.append(node)
            for neighbor in sorted(self.adj.get(node, [])):
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        return order
    
    def dfs(self, start):
        """深度优先搜索"""
        visited = set()
        order = []
        self._dfs_helper(start, visited, order)
        return order
    
    def _dfs_helper(self, node, visited, order):
        visited.add(node)
        order.append(node)
        for neighbor in sorted(self.adj.get(node, [])):
            if neighbor not in visited:
                self._dfs_helper(neighbor, visited, order)

# 构建图
g = Graph()
edges = [("A", "B"), ("A", "C"), ("B", "D"), ("B", "E"), ("C", "F"), ("D", "E"), ("E", "F")]
for u, v in edges:
    g.add_edge(u, v)

print("图的边:", edges)
print(f"\nBFS (从 A 出发): {g.bfs('A')}")
print(f"DFS (从 A 出发): {g.dfs('A')}")

# 最短路径（BFS）
def shortest_path(graph, start, end):
    queue = deque([(start, [start])])
    visited = {start}
    while queue:
        node, path = queue.popleft()
        if node == end:
            return path
        for neighbor in graph.adj.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    return None

path = shortest_path(g, "A", "F")
print(f"\nA 到 F 的最短路径: {' → '.join(path)}")

点击「运行」或「提交代码」查看结果

📖 查看本课说明

第 8 关：图的遍历

Python/C++ · 进阶 · 《算法入门》

图的遍历

本关为 Python/C++，浏览器无法真正编译运行，请在本地环境验证代码。