### Python 实现图、树、栈、队列以及 DFS 和 BFS 以下是基于 Python 编写的实现方案，涵盖了图、树、栈、队列的数据结构定义，以及深度优先搜索（DFS）和广度优先搜索（BFS）算法的具体实现。 --- #### 1. **图的表示** 图可以通过邻接表的方式进行表示。以下是一个简单的无向图实现： ```python class Graph: def __init__(self): self.graph = {} def add_edge(self, u, v): if u not in self.graph: self.graph[u] = [] if v not in self.graph: self.graph[v] = [] self.graph[u].append(v) self.graph[v].append(u) def get_graph(self): return self.graph ``` 创建一个具有 10 个节点的简单图： ```python g = Graph() edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6), (3, 7), (4, 8), (5, 9)] for edge in edges: g.add_edge(*edge) print(g.get_graph()) ``` --- #### 2. **树的表示** 树可以看作一种特殊的图，这里我们使用字典来构建一棵二叉树： ```python class TreeNode: def __init__(self, value=0, left=None, right=None): self.value = value self.left = left self.right = right def build_tree(): root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(3) root.left.left = TreeNode(4) root.left.right = TreeNode(5) root.right.left = TreeNode(6) root.right.right = TreeNode(7) return root ``` --- #### 3. **栈的实现** 栈遵循后进先出（LIFO）原则，可以用列表轻松实现： ```python class Stack: def __init__(self): self.stack = [] def push(self, item): self.stack.append(item) def pop(self): if not self.is_empty(): return self.stack.pop() def is_empty(self): return len(self.stack) == 0 def peek(self): if not self.is_empty(): return self.stack[-1] def size(self): return len(self.stack) ``` --- #### 4. **队列的实现** 队列遵循先进先出（FIFO）原则，也可以用列表实现： ```python class Queue: def __init__(self): self.queue = [] def enqueue(self, item): self.queue.append(item) def dequeue(self): if not self.is_empty(): return self.queue.pop(0) def is_empty(self): return len(self.queue) == 0 def front(self): if not self.is_empty(): return self.queue[0] def size(self): return len(self.queue) ``` --- #### 5. **DFS 的实现** 深度优先搜索利用栈或者递归来实现。以下是两种方式的实现： ##### 使用递归实现 DFS： ```python def dfs_recursive(graph, start, visited=None): if visited is None: visited = set() visited.add(start) print(start, end=" ") for neighbor in graph[start]: if neighbor not in visited: dfs_recursive(graph, neighbor, visited) ``` ##### 使用显式栈实现 DFS： ```python def dfs_iterative(graph, start): stack = Stack() visited = set() stack.push(start) while not stack.is_empty(): node = stack.pop() if node not in visited: visited.add(node) print(node, end=" ") for neighbor in reversed(graph[node]): if neighbor not in visited: stack.push(neighbor) ``` --- #### 6. **BFS 的实现** 广度优先搜索利用队列实现： ```python def bfs(graph, start): queue = Queue() visited = set() queue.enqueue(start) visited.add(start) while not queue.is_empty(): node = queue.dequeue() print(node, end=" ") for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.enqueue(neighbor) ``` --- #### 7. **分析完备性、最优性和复杂度** | 特性 | DFS | BFS | |--------------|------------------------------------|------------------------------------| | **完备性** | 如果图是有限的，则总是能找到解[^1] | 总是可以找到解 | | **最优性** | 不一定是最短路径 | 可以保证找到最短路径 | | **时间复杂度**| O(V + E)，其中 V 是顶点数，E 是边数 | O(V + E)[^3] | | **空间复杂度**| O(V) | O(V) | 对于特定场景下的性能对比，例如解决八数码问题时，启发式方法如 A* 明显优于传统的 BFS 方法[^5]。 ---