4. 图搜索基础：图论基本概念、图的存储方式

各位同学，欢迎来到图搜索这一章。说实话，图论这东西，我当年刚接触时也觉得挺抽象的。一堆点和线，能干啥？直到我在做机器人路径规划项目时，遇到一个实际问题——机器人要在仓库里从A点走到B点，中间有货架、有障碍物，怎么走最近？这时候我才意识到，图就是解决这类问题的利器。

这一节，咱们先把图论的基本概念捋清楚，再聊聊图的两种主流存储方式。嗯，这些都是后面做路径搜索的基石，打牢了才能走远。

4.1 图论基本概念

图是什么？说白了，就是一堆节点（也叫顶点）和连接它们的边。你想想看，地图上的每个路口就是一个节点，路口之间的道路就是边。机器人要从一个路口到另一个路口，本质上就是在图上找一条路径。

我习惯把图拆成几个核心要素来理解：

• 顶点（Vertex）：图中的基本单元，通常用圆圈表示。在路径规划里，顶点可以代表位置点、状态或者决策点。
• 边（Edge）：连接两个顶点的线，表示它们之间存在某种关系。比如两个路口之间有路相通。
• 有向图 vs 无向图：边有方向就是有向图，没方向就是无向图。现实中，单行道就是有向边，双向道就是无向边。
• 权重（Weight）：边上的数值，代表代价。比如距离、时间、能耗等。路径规划的核心就是找权重和最小的路径。

我在项目中遇到过一个问题：地图明明画好了，但机器人总是绕远路。后来发现，是因为我把无向图当有向图处理了，导致某些双向道路只允许单向通行。嗯，这个坑你们要记住。

4.2 图的存储方式

图在计算机里怎么存？这是个实际问题。你想想看，地图可能有几百个路口、上千条道路，总不能手动画吧？我们需要一种高效的数据结构来存储图。常用的有两种：邻接矩阵和邻接表。

4.2.1 邻接矩阵

邻接矩阵，说白了就是一个二维数组。假设图有 n 个顶点，我们就用一个 n×n 的矩阵来表示。矩阵的第 i 行第 j 列的元素，表示顶点 i 到顶点 j 是否有边（或者边的权重）。

举个例子，一个简单的无向图：

顶点：A, B, C, D
边：A-B, A-C, B-D, C-D

邻接矩阵（用0/1表示有无边）：
    A  B  C  D
A   0  1  1  0
B   1  0  0  1
C   1  0  0  1
D   0  1  1  0

如果是带权图，就把1换成具体的权重值，没有边的地方用无穷大（或者一个很大的数）表示。

4.2.2 邻接表

邻接表是另一种思路。它为每个顶点维护一个链表（或者数组），里面存放该顶点能到达的所有邻居顶点。还是上面那个例子：

顶点A: [B, C]
顶点B: [A, D]
顶点C: [A, D]
顶点D: [B, C]

如果是带权图，链表里不仅要存邻居顶点，还要存边的权重：

顶点A: [(B, 5), (C, 3)]
顶点B: [(A, 5), (D, 2)]
顶点C: [(A, 3), (D, 4)]
顶点D: [(B, 2), (C, 4)]

邻接表的空间复杂度是 O(n + e)，其中 e 是边的数量。对于稀疏图，这比邻接矩阵省很多空间。

4.3 代码实现示例

光说不练假把式。我习惯用 Python 来实现这两种存储方式，因为写起来快，调试也方便。下面给个简单的示例：

# 邻接矩阵实现
class GraphMatrix:
    def __init__(self, n):
        self.n = n
        self.matrix = [[0] * n for _ in range(n)]
    
    def add_edge(self, u, v, weight=1):
        self.matrix[u][v] = weight
        self.matrix[v][u] = weight  # 无向图
    
    def has_edge(self, u, v):
        return self.matrix[u][v] != 0

# 邻接表实现
class GraphList:
    def __init__(self, n):
        self.n = n
        self.adj = [[] for _ in range(n)]
    
    def add_edge(self, u, v, weight=1):
        self.adj[u].append((v, weight))
        self.adj[v].append((u, weight))  # 无向图
    
    def get_neighbors(self, u):
        return self.adj[u]

你看，代码其实很简单。但实际项目中，我建议你根据图的规模来选。如果顶点数少于100，邻接矩阵用着挺舒服。如果超过1000，还是老老实实用邻接表吧。

4.4 小结

这一节我们聊了图的基本概念和两种存储方式。图论这东西，刚开始可能觉得有点绕，但多画几个图、多写几行代码就熟了。我个人觉得，理解图的关键在于想清楚顶点和边分别代表什么。在路径规划里，顶点就是位置点，边就是可通行的路径，权重就是代价。后面讲 Dijkstra、A* 这些算法时，你会发现它们都是在图上做文章。

下一节，我们会正式进入图搜索算法。到时候，这些存储方式就会派上用场了。嗯，做好准备。

---

公众号:蓝海资料掘金营，微信deep3321