第4章 图论基础
图是一种比树更复杂的非线性数据结构，它由顶点和边组成。图可以用来表示各种关系网络，比如社交网络、交通网络、计算机网络等。本章将介绍图的基本概念、表示方法和遍历算法。
4.1 图的基本概念
Graph Structure
图由顶点集合V和边集合E组成，记作G=(V,E)。顶点是图中的数据元素，边是顶点之间的连接关系。根据边是否有方向，图分为无向图和有向图。无向图的边没有方向，两个顶点之间可以双向通行。有向图的边有方向，从一个顶点指向另一个顶点。
根据边是否带有权值，图分为无权图和带权图。无权图的边只表示连接关系，没有额外的数值信息。带权图的边带有权值，可以表示距离、成本、时间等信息。带权图也叫网络图。
class Graph:
def __init__(self, directed=False):
self.directed = directed
self.vertices = set()
self.edges = {}
def add_vertex(self, vertex):
self.vertices.add(vertex)
if vertex not in self.edges:
self.edges[vertex] = {}
def add_edge(self, v1, v2, weight=1):
self.add_vertex(v1)
self.add_vertex(v2)
self.edges[v1][v2] = weight
if not self.directed:
self.edges[v2][v1] = weight
def get_vertices(self):
return list(self.vertices)
def get_edges(self):
edge_list = []
for v1 in self.edges:
for v2 in self.edges[v1]:
if not self.directed and (v2, v1) in edge_list:
continue
edge_list.append((v1, v2, self.edges[v1][v2]))
return edge_list
def get_neighbors(self, vertex):
return self.edges.get(vertex, {})
图的几个重要概念需要理解。度是指与顶点相连的边的数量。在有向图中，度分为入度和出度。入度是指指向该顶点的边的数量，出度是指从该顶点发出的边的数量。路径是从一个顶点到另一个顶点的顶点序列，序列中相邻顶点之间有边相连。路径的长度是路径上边的数量或权值之和。简单路径是不包含重复顶点的路径。环是起点和终点相同的路径。连通是指两个顶点之间存在路径。连通图是指任意两个顶点之间都连通的图。
4.2 图的表示方法
图的存储方式主要有邻接矩阵和邻接表两种。邻接矩阵使用二维数组表示图，矩阵的行和列对应顶点，矩阵元素表示顶点之间是否有边。邻接矩阵的优点是判断两个顶点是否相连只需O(1)时间，缺点是空间复杂度为O(V²)，对于稀疏图浪费空间。
class AdjacencyMatrix:
def __init__(self, num_vertices, directed=False):
self.num_vertices = num_vertices
self.directed = directed
self.matrix = [[0] * num_vertices for _ in range(num_vertices)]
def add_edge(self, v1, v2, weight=1):
self.matrix[v1][v2] = weight
if not self.directed:
self.matrix[v2][v1] = weight
def has_edge(self, v1, v2):
return self.matrix[v1][v2] != 0
def get_weight(self, v1, v2):
return self.matrix[v1][v2]
def get_neighbors(self, v):
neighbors = []
for i in range(self.num_vertices):
if self.matrix[v][i] != 0:
neighbors.append(i)
return neighbors
def display(self):
for row in self.matrix:
print(' '.join(str(x) for x in row))
graph = AdjacencyMatrix(5)
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 3)
graph.add_edge(2, 4)
graph.display()
邻接表使用数组或字典存储每个顶点的邻居列表。邻接表的优点是空间复杂度为O(V+E)，适合稀疏图。缺点是判断两个顶点是否相连需要遍历邻居列表，时间复杂度为O(V)。
class AdjacencyList:
def __init__(self, directed=False):
self.directed = directed
self.vertices = {}
def add_vertex(self, vertex):
if vertex not in self.vertices:
self.vertices[vertex] = []
def add_edge(self, v1, v2, weight=1):
self.add_vertex(v1)
self.add_vertex(v2)
self.vertices[v1].append((v2, weight))
if not self.directed:
self.vertices[v2].append((v1, weight))
def get_neighbors(self, vertex):
return self.vertices.get(vertex, [])
def display(self):
for vertex in self.vertices:
neighbors = ', '.join(f'{v}({w})' for v, w in self.vertices[vertex])
print(f'{vertex}: [{neighbors}]')
graph = AdjacencyList()
graph.add_edge('A', 'B', 1)
graph.add_edge('A', 'C', 2)
graph.add_edge('B', 'D', 3)
graph.add_edge('C', 'D', 4)
graph.display()
选择哪种表示方法取决于具体应用。如果图比较稠密，边的数量接近V²，邻接矩阵更合适。如果图比较稀疏，边的数量远小于V²，邻接表更节省空间。如果需要频繁查询两个顶点是否相连，邻接矩阵效率更高。如果需要频繁遍历某个顶点的所有邻居，邻接表效率更高。
4.3 广度优先搜索
Graph Traversal
广度优先搜索是一种图的遍历算法，它从起始顶点开始，先访问所有邻居，然后访问邻居的邻居，以此类推，层层向外扩展。BFS使用队列来保证按层次顺序访问顶点，保证先访问距离起始顶点近的顶点。
def bfs(graph, start):
visited = set()
queue = [start]
result = []
while queue:
vertex = queue.pop(0)
if vertex in visited:
continue
visited.add(vertex)
result.append(vertex)
for neighbor in graph.get_neighbors(vertex):
if neighbor not in visited:
queue.append(neighbor)
return result
def bfs_shortest_path(graph, start, end):
visited = set([start])
queue = [(start, [start])]
while queue:
vertex, path = queue.pop(0)
if vertex == end:
return path
for neighbor in graph.get_neighbors(vertex):
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, path + [neighbor]))
return None
BFS的一个重要应用是寻找无权图中的最短路径。因为BFS按层次遍历，第一次到达目标顶点时，经过的路径长度最小。在社交网络中，BFS可以找到两个人之间的最短关系链。在迷宫问题中，BFS可以找到从起点到终点的最短路径。
BFS的时间复杂度为O(V+E)，因为每个顶点和每条边最多被访问一次。空间复杂度为O(V)，因为需要存储访问标记和队列。
4.4 深度优先搜索
深度优先搜索也是一种图的遍历算法，它从起始顶点开始，沿着一条路径尽可能深入，直到无法继续前进，然后回溯到上一个顶点，继续探索其他路径。DFS使用栈或递归来实现，体现出回溯的思想。
def dfs_recursive(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
result = [start]
for neighbor in graph.get_neighbors(start):
if neighbor not in visited:
result.extend(dfs_recursive(graph, neighbor, visited))
return result
def dfs_iterative(graph, start):
visited = set()
stack = [start]
result = []
while stack:
vertex = stack.pop()
if vertex in visited:
continue
visited.add(vertex)
result.append(vertex)
for neighbor in reversed(graph.get_neighbors(vertex)):
if neighbor not in visited:
stack.append(neighbor)
return result
DFS的应用比BFS更加广泛。检测图的连通性，判断图中是否有环，寻找拓扑排序，检测二分图等都可以使用DFS。DFS还可以用于求解迷宫问题，但找到的路径不一定是最短的。
def has_cycle_dfs(graph):
def dfs(vertex, visited, parent):
visited.add(vertex)
for neighbor in graph.get_neighbors(vertex):
if neighbor not in visited:
if dfs(neighbor, visited, vertex):
return True
elif neighbor != parent:
return True
return False
visited = set()
for vertex in graph.vertices:
if vertex not in visited:
if dfs(vertex, visited, None):
return True
return False
DFS的时间复杂度为O(V+E)，空间复杂度为O(V)。递归实现的DFS需要额外的栈空间，深度可达V。对于深度很大的图，使用迭代实现可以避免栈溢出。
4.5 最短路径算法
Shortest Path
在带权图中寻找两个顶点之间的最短路径是一个经典问题。Dijkstra算法是最著名的最短路径算法，它可以找到从一个顶点到其他所有顶点的最短路径。Dijkstra算法使用贪心策略，每次选择距离最近的未访问顶点，更新其邻居的距离。
import heapq
def dijkstra(graph, start):
distances = {vertex: float('inf') for vertex in graph.vertices}
distances[start] = 0
visited = set()
pq = [(0, start)]
while pq:
current_dist, vertex = heapq.heappop(pq)
if vertex in visited:
continue
visited.add(vertex)
for neighbor, weight in graph.get_neighbors(vertex):
new_dist = current_dist + weight
if new_dist < distances[neighbor]:
distances[neighbor] = new_dist
heapq.heappush(pq, (new_dist, neighbor))
return distances
graph = AdjacencyList(directed=True)
graph.add_edge('A', 'B', 4)
graph.add_edge('A', 'C', 2)
graph.add_edge('B', 'C', 1)
graph.add_edge('B', 'D', 5)
graph.add_edge('C', 'D', 8)
graph.add_edge('C', 'E', 10)
graph.add_edge('D', 'E', 2)
distances = dijkstra(graph, 'A')
print("从A出发的最短距离:")
for vertex, dist in distances.items():
print(f" 到{vertex}: {dist}")
Dijkstra算法的时间复杂度为O(V²)或O(E log V)，取决于实现方式。使用优先队列可以将时间复杂度优化到O(E log V)。Dijkstra算法只能用于边权为正的图，对于边权为负的图，需要使用Bellman-Ford算法。
如果只需要两个顶点之间的最短路径，而不需要到所有顶点的最短路径，可以使用A算法。A算法在Dijkstra算法的基础上加入了启发式信息，可以更快地找到目标路径。
4.6 拓扑排序
Topological Sort
拓扑排序是针对有向无环图的一种排序方法，它将图中所有顶点排成一个线性序列，使得图中每一条边的起点在终点之前。拓扑排序常用于任务调度、课程安排等场景，需要确定任务的执行顺序。
def topological_sort(graph):
def dfs(vertex, visited, stack, temp):
if vertex in temp:
raise ValueError("图中存在环，无法进行拓扑排序")
if vertex in visited:
return
temp.add(vertex)
for neighbor in graph.get_neighbors(vertex):
dfs(neighbor, visited, stack, temp)
temp.remove(vertex)
visited.add(vertex)
stack.append(vertex)
visited = set()
stack = []
for vertex in graph.vertices:
if vertex not in visited:
dfs(vertex, visited, stack, [])
return stack[::-1]
graph = AdjacencyList(directed=True)
graph.add_edge('A', 'B')
graph.add_edge('A', 'C')
graph.add_edge('B', 'D')
graph.add_edge('C', 'D')
order = topological_sort(graph)
print("拓扑排序结果:", ' -> '.join(order))
拓扑排序的另一种实现方法是Kahn算法，它基于入度的概念。首先找到所有入度为0的顶点，将它们加入结果序列。然后移除这些顶点的出边，更新其他顶点的入度。重复这个过程，直到所有顶点都被加入结果序列。如果中途无法找到入度为0的顶点，说明图中存在环。
def kahn_topological_sort(graph):
in_degree = {vertex: 0 for vertex in graph.vertices}
for vertex in graph.vertices:
for neighbor, _ in graph.get_neighbors(vertex):
in_degree[neighbor] += 1
queue = [v for v, d in in_degree.items() if d == 0]
result = []
while queue:
vertex = queue.pop(0)
result.append(vertex)
for neighbor, _ in graph.get_neighbors(vertex):
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
if len(result) != len(graph.vertices):
raise ValueError("图中存在环，无法进行拓扑排序")
return result
拓扑排序的时间复杂度为O(V+E)。两种算法各有特点。DFS算法通过深度优先遍历实现，代码简洁。Kahn算法更直观，易于理解，并且可以同时检测图中是否有环。
本章我们学习了图的基本概念、表示方法和遍历算法。图是表达复杂关系的强大工具，社交网络、交通网络、依赖关系等都可以用图来表示。BFS和DFS是两种基本的图遍历算法，各有不同的应用场景。Dijkstra算法解决了最短路径问题，拓扑排序解决了依赖关系问题。下一章我们将学习排序算法，包括冒泡排序、快速排序等多种经典的排序方法。
预览时标签不可点