图论算法实战：图的表示与遍历算法的陷阱与误区

# 1. 图论算法基础**

图论算法是计算机科学中用于解决与图结构相关问题的算法。图是一种数据结构，它由一组顶点和连接这些顶点的边组成。图论算法广泛应用于各种领域，例如网络路由、社交网络分析和图像处理。

图论算法的基础概念包括：

* **顶点：**图中的基本元素，表示一个对象或实体。
* **边：**连接两个顶点的线段，表示顶点之间的关系或权重。
* **权重：**与边关联的数值，表示边上的成本或距离。
* **路径：**顶点之间的边序列，表示从一个顶点到另一个顶点的连接。
* **连通性：**图中顶点之间的连接程度，表示顶点是否可以相互到达。

# 2. 图的表示

图的表示是图论算法的基础，它决定了算法的时间和空间复杂度。本章节将介绍三种常用的图的表示方法：邻接矩阵、邻接表和邻接多重表。

### 2.1 邻接矩阵

邻接矩阵是一种使用二维数组来表示图的结构的方法。对于一个有n个顶点的图，其邻接矩阵是一个n*n的矩阵，其中矩阵元素a[i][j]表示顶点i和顶点j之间的边权重。如果图中不存在边，则a[i][j]为0。

**优点：**

* 查询边权重方便
* 判断两个顶点是否相邻方便

**缺点：**

* 对于稀疏图（边数远小于顶点数），空间浪费严重
* 插入或删除边需要更新整行或整列

**代码示例：**

class AdjacencyMatrix:
    def __init__(self, n):
        self.n = n
        self.matrix = [[0 for _ in range(n)] for _ in range(n)]

    def add_edge(self, i, j, weight):
        self.matrix[i][j] = weight

    def get_weight(self, i, j):
        return self.matrix[i][j]

### 2.2 邻接表

邻接表是一种使用链表来表示图的结构的方法。对于一个有n个顶点的图，其邻接表是一个长度为n的数组，其中每个元素是一个链表，表示与该顶点相邻的顶点。

**优点：**

* 对于稀疏图，空间利用率高
* 插入或删除边方便

**缺点：**

* 查询边权重不方便
* 判断两个顶点是否相邻需要遍历链表

**代码示例：**

class AdjacencyList:
    def __init__(self, n):
        self.n = n
        self.adj_list = [[] for _ in range(n)]

    def add_edge(self, i, j, weight):
        self.adj_list[i].append((j, weight))

    def get_neighbors(self, i):
        return self.adj_list[i]

### 2.3 邻接多重表

邻接多重表是一种使用字典来表示图的结构的方法。对于一个有n个顶点的图，其邻接多重表是一个长度为n的字典，其中每个键是一个顶点，值是一个字典，表示与该顶点相邻的顶点及其边权重。

**优点：**

* 对于稀疏图，空间利用率高
* 插入或删除边方便
* 查询边权重方便

**缺点：**

* 判断两个顶点是否相邻需要遍历字典

**代码示例：**

class AdjacencyMultimap:
    def __init__(self, n):
        self.n = n
        self.adj_map = {i: {} for i in range(n)}

    def add_edge(self, i, j, weight):
        self.adj_map[i][j] = weight

    def get_weight(self, i, j):
        return self.adj_map[i].get(j, 0)

**表格对比：**

| 表示方法 | 空间复杂度 | 时间复杂度 | 查询边权重 | 判断相邻 | 插入/删除边 |
|---|---|---|---|---|---|
| 邻接矩阵 | O(n^2) | O(1) | O(1) | O(1) | O(n) |
| 邻接表 | O(V+E) | O(V+E) | O(E) | O(V) | O(1) |
| 邻接多重表 | O(V+E) | O(V+E) | O(1) | O(V) | O(1) |

**选择建议：**

* 对于稠密图（边数接近顶点数），邻接矩阵更合适。
* 对于稀疏图（边数远小于顶点数），邻接表或邻接多重表更合适。
* 如果需要频繁查询边权重，邻接矩阵或邻接多重表更合适。
* 如果需要频繁插入或删除边，邻接表或邻接多重表更合适。

# 3. 图的遍历算法**

图的遍历算法是图论中非常重要的算法，它可以帮助我们遍历图中的所有节点和边。图的遍历算法有很多种，其中最常用的两种是深度优先搜索（DFS）和广度优先搜索（BFS）。

### 3.1 深度优先搜索（DFS）

DFS是一种递归算法，它从一个起始节点开始，沿着一条路径一直向下遍历，直到到达叶子节点。然后，它回溯到上一个未访问的节点，并继续沿着另一条路径向下遍历。

#### 3.1.1 递归实现

DFS的递归实现非常简单，如下所示：

def dfs(graph, start):
    visited.add(start)
    print(start)
    for neighbor in graph[start]:
        if neighbor not in visited: