1. 什么是图？ #

图

1.1 图的基本概念 #

图（Graph）是由顶点（Vertex/Node）和边（Edge/Relationship）组成的数据结构，用来表示事物之间的关系。

想象一下，如果你要画一张社交网络图：

• 顶点就是每个人（用圆圈表示）
• 边就是人与人之间的关系（用线表示，比如"朋友"、"同事"）

这就是图的基本概念！

1.2 为什么需要图？ #

在日常生活中，我们经常遇到需要表示关系的情况：

• 社交网络：谁和谁是朋友
• 地图导航：哪些地点之间有道路连接
• 推荐系统：用户喜欢哪些商品
• 知识图谱：概念之间的关联关系

图数据结构就是为了高效地表示和查询这些关系而设计的。

1.3 图的基本术语 #

在学习图之前，我们需要了解一些基本术语：

• 顶点（Vertex/Node）：图中的基本元素，表示实体

  • 例如：人、地点、产品、概念
  • 在图中通常用圆圈或方框表示

• 边（Edge/Relationship）：连接两个顶点的线，表示关系

  • 例如：朋友关系、道路连接、购买关系、包含关系
  • 在图中通常用箭头或线段表示

• 度（Degree）：与顶点相连的边的数量

  • 例如：一个人的朋友数量就是他的度
  • 有向图中分为"入度"（指向该顶点的边数）和"出度"（从该顶点出发的边数）

• 路径（Path）：从一个顶点到另一个顶点经过的边序列

  • 例如：从A到B，经过A→C→D→B，这就是一条路径
  • 路径的长度是经过的边的数量

• 环（Cycle）：起点和终点相同的路径

  • 例如：A→B→C→A，形成了一个环

2. 图的分类 #

图可以根据不同的特征进行分类。了解这些分类有助于我们选择合适的图结构来解决问题。

2.1 按边的方向分类 #

2.1.1 无向图（Undirected Graph） #

无向图中的边没有方向，表示双向关系。

特点：

• 如果A和B之间有边，那么可以从A到B，也可以从B到A
• 适合表示对称关系，如：朋友关系、合作关系

实际应用：

• Facebook的好友关系（如果A是B的朋友，那么B也是A的朋友）
• 城市之间的道路连接（通常可以双向通行）

示例：

A - B

这表示A和B之间有连接，但没有方向。

2.1.2 有向图（Directed Graph） #

有向图中的边有方向，表示单向关系。

特点：

• 如果A→B有边，只能从A到B，不能从B到A（除非有B→A的边）
• 适合表示非对称关系，如：关注关系、依赖关系

实际应用：

• Twitter的关注关系（A关注B，但B不一定关注A）
• 网页之间的链接（A页面链接到B页面）
• 任务依赖关系（任务A完成后才能执行任务B）

示例：

A → B

这表示从A到B有方向，但B不能直接到A。

2.2 按边的权重分类 #

2.2.1 无权图（Unweighted Graph） #

无权图中的边没有权重，只表示是否存在关系。

特点：

• 边只表示"有"或"没有"关系
• 不关心关系的强度或成本

实际应用：

• 社交网络中的朋友关系（只关心是不是朋友，不关心亲密度）
• 网页之间的链接（只关心有没有链接）

2.2.2 加权图（Weighted Graph） #

加权图中的边有权重，表示关系的强度或成本。

特点：

• 每条边都有一个数值（权重）
• 权重可以表示距离、成本、强度等

实际应用：

• 地图导航（边的权重表示距离或时间）
• 社交网络（边的权重表示亲密度）
• 推荐系统（边的权重表示相似度）

示例：

A --(5)--> B  # 表示从A到B的距离是5，或亲密度是5分

2.3 特殊图类型 #

在实际应用中，我们还会遇到一些特殊的图类型：

• 连通图：任意两个顶点都有路径相连

  • 例如：一个社交网络中，所有人都可以通过朋友关系连接起来

• 树：没有环的连通图（特殊图）

  • 例如：公司的组织架构图、文件系统的目录结构

• 完全图：每对顶点之间都有边连接

  • 例如：一个小团队中，每个人都认识其他人

3. 图的表示方法 #

在计算机中，我们需要用数据结构来表示图。主要有两种常用的方法：邻接矩阵和邻接表。

3.1 前置知识：什么是邻接？ #

邻接（Adjacency）指的是两个顶点之间有边直接相连。如果顶点A和B之间有边，我们就说A和B是邻接的。

3.2 邻接矩阵（Adjacency Matrix） #

邻接矩阵

邻接矩阵是用二维数组来表示图的方法。

工作原理：

• 用一个二维数组（矩阵）存储图
• 如果顶点i到顶点j有边，则matrix[i][j] = 1（或权重值）
• 如果没有边，则matrix[i][j] = 0（或无穷大）

优点：

• 查找两个顶点之间是否有边非常快（O(1)）
• 实现简单，容易理解

缺点：

• 占用空间大（O(V²)，V是顶点数）
• 适合稠密图（边很多），不适合稀疏图（边很少）

示例：

图结构：
A → B
↓   ↑
C → D

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

Python实现：

# 使用邻接矩阵表示有向图
# 创建一个4x4的矩阵，表示4个顶点（A、B、C、D）
# 矩阵中的1表示有边，0表示无边

# 定义顶点名称
vertices = ['A', 'B', 'C', 'D']  # 顶点列表

# 创建邻接矩阵（各行对应每个顶点的出边），1表示有边，0表示无边
adjacency_matrix = [
    [0, 1, 1, 0],  # A到B、C有边
    [0, 0, 0, 0],  # B没有出边
    [0, 0, 0, 1],  # C到D有边
    [0, 1, 0, 0]   # D到B有边
]

# 打印"邻接矩阵："标题
print("邻接矩阵：")
# 打印表头空格和所有顶点名称
print("   ", end="")
for v in vertices:
    # 以3个字符宽度打印每个顶点名
    print(f"{v:>3}", end="")
print()

# 枚举每一行及其对应顶点
for i, row in enumerate(adjacency_matrix):
    # 打印当前行的顶点名，右对齐
    print(f"{vertices[i]:>3}", end="")
    # 打印当前行的所有边（0或1），每个宽度为3
    for val in row:
        print(f"{val:>3}", end="")
    # 换行，打印下一行
    print()

# 定义函数：判断两个顶点之间是否有边
def has_edge(matrix, from_vertex, to_vertex):
    # 获取from_vertex的下标
    from_idx = vertices.index(from_vertex)
    # 获取to_vertex的下标
    to_idx = vertices.index(to_vertex)
    # 返回这两个顶点间的邻接状态（1为有边，0为无边）
    return matrix[from_idx][to_idx] == 1

# 测试A到B是否有边
print(f"\nA到B是否有边：{has_edge(adjacency_matrix, 'A', 'B')}")
# 测试B到A是否有边
print(f"B到A是否有边：{has_edge(adjacency_matrix, 'B', 'A')}")

3.3 邻接表（Adjacency List） #

邻接表

邻接表是用数组+链表（或字典）来表示图的方法。

工作原理：

• 为每个顶点维护一个列表，存储与该顶点相邻的所有顶点
• 可以用字典实现：{顶点: [相邻顶点列表]}

优点：

• 占用空间小（O(V+E)，V是顶点数，E是边数）
• 适合稀疏图（边很少）
• 遍历某个顶点的所有邻居很快

缺点：

• 查找两个顶点之间是否有边较慢（O(V)）
• 实现稍微复杂一些

示例：

图结构：
A → B → C
B → D
C → B
D → C

邻接表：
A: [B, C]
B: [D]
C: [B]
D: [C]

Python实现：

# 使用邻接表表示有向图
# 用字典存储，键是顶点，值是该顶点的所有邻居列表

# 创建邻接表
adjacency_list = {
    'A': ['B', 'C'],  # A的邻居是B和C
    'B': ['D'],       # B的邻居是D
    'C': ['B'],       # C的邻居是B
    'D': ['C']        # D的邻居是C
}

# 打印邻接表
print("邻接表：")
for vertex, neighbors in adjacency_list.items():
    print(f"{vertex}: {neighbors}")

# 获取某个顶点的所有邻居
def get_neighbors(adj_list, vertex):
    """获取vertex的所有邻居"""
    return adj_list.get(vertex, [])

# 检查两个顶点之间是否有边
def has_edge(adj_list, from_vertex, to_vertex):
    """检查从from_vertex到to_vertex是否有边"""
    neighbors = adj_list.get(from_vertex, [])
    return to_vertex in neighbors

# 测试
print(f"\nA的邻居：{get_neighbors(adjacency_list, 'A')}")
print(f"A到B是否有边：{has_edge(adjacency_list, 'A', 'B')}")
print(f"B到A是否有边：{has_edge(adjacency_list, 'B', 'A')}")

3.4 两种方法的对比 #

特性	邻接矩阵	邻接表
空间复杂度	O(V²)	O(V+E)
查找边	O(1)	O(V)
遍历邻居	O(V)	O(度)
适合场景	稠密图	稀疏图
实现难度	简单	中等

选择建议：

• 如果图很稠密（边很多），使用邻接矩阵
• 如果图很稀疏（边很少），使用邻接表
• 大多数实际应用中，图都是稀疏的，所以邻接表更常用

4. 图的实现 #

图的实现

现在让我们用Python实现一个完整的图类，包含添加顶点、添加边、查找邻居等基本操作。

# 定义一个图类
class Graph:
    # 初始化函数，directed表示图是否为有向图
    def __init__(self, directed=False):
        # 顶点存储字典
        self.vertices = {}
        # 边存储字典
        self.edges = {}
        # 是否为有向图
        self.directed = directed

    # 添加顶点方法，vertex_id为顶点标识，data为可选数据
    def add_vertex(self, vertex_id, data=None):
        # 如果顶点不存在，则添加到字典中
        if vertex_id not in self.vertices:
            self.vertices[vertex_id] = data
            # 初始化该顶点的边列表
            self.edges[vertex_id] = []

    # 添加边方法，from_vertex为起点，to_vertex为终点，weight为权重
    def add_edge(self, from_vertex, to_vertex, weight=1):
        # 如果起点不存在，则先添加起点
        if from_vertex not in self.vertices:
            self.add_vertex(from_vertex)
        # 如果终点不存在，则先添加终点
        if to_vertex not in self.vertices:
            self.add_vertex(to_vertex)
        # 如果边不存在，则添加边到起点的边列表
        if (to_vertex, weight) not in self.edges[from_vertex]:
            self.edges[from_vertex].append((to_vertex, weight))
        # 如果是无向图，还需要添加一条反向边
        if not self.directed:
            if (from_vertex, weight) not in self.edges[to_vertex]:
                self.edges[to_vertex].append((from_vertex, weight))

    # 获取某个顶点的邻居
    def get_neighbors(self, vertex_id):
        # 返回对应顶点的邻居列表
        return self.edges.get(vertex_id, [])

    # 获取某个顶点的度
    def get_degree(self, vertex_id):
        # 返回邻居的数量
        return len(self.edges.get(vertex_id, []))

    # 打印图的结构信息
    def print_graph(self):
        # 打印顶点数量
        print(f"顶点数量：{len(self.vertices)}")
        # 打印图类型（有向或无向）
        print(f"图类型：{'有向图' if self.directed else '无向图'}")
        # 遍历所有顶点及其邻居，打印边信息
        for from_vertex, neighbors in self.edges.items():
            for to_vertex, weight in neighbors:
                print(f"{from_vertex} → {to_vertex} (权重: {weight})")

# 创建一个有向图对象
graph = Graph(directed=True)
# 添加顶点A
graph.add_vertex('A')
# 添加顶点B
graph.add_vertex('B')
# 添加顶点C
graph.add_vertex('C')
# 添加顶点D
graph.add_vertex('D')
# 添加边A->B，权重1
graph.add_edge('A', 'B', weight=1)
# 添加边A->C，权重2
graph.add_edge('A', 'C', weight=2)
# 添加边C->D，权重3
graph.add_edge('C', 'D', weight=3)
# 添加边D->B，权重1
graph.add_edge('D', 'B', weight=1)
# 打印有向图结构
graph.print_graph()

# 创建一个无向图对象
undirected_graph = Graph(directed=False)
# 添加顶点A
undirected_graph.add_vertex('A')
# 添加顶点B
undirected_graph.add_vertex('B')
# 添加顶点C
undirected_graph.add_vertex('C')
# 添加边A-B，权重1
undirected_graph.add_edge('A', 'B', weight=1)
# 添加边B-C，权重2
undirected_graph.add_edge('B', 'C', weight=2)
# 打印无向图结构
undirected_graph.print_graph()

5. 图的遍历算法 #

图的遍历

图的遍历是指访问图中的每个顶点，且每个顶点只访问一次。有两种基本的遍历方法：深度优先搜索（DFS）和广度优先搜索（BFS）。

5.1 前置知识：递归和队列 #

在理解遍历算法之前，我们需要了解：

• 递归（Recursion）：函数调用自身
• 队列（Queue）：先进先出（FIFO）的数据结构

5.2 深度优先搜索（DFS） #

深度优先搜索（Depth-First Search, DFS）就像走迷宫时，选择一条路一直走到底，走不通再回头。

工作原理：

1. 从起始顶点开始
2. 访问该顶点，标记为已访问
3. 选择一个未访问的邻居，递归访问
4. 如果所有邻居都已访问，回溯到上一个顶点
5. 重复直到所有顶点都被访问

实际应用：

• 查找路径
• 检测环
• 拓扑排序

Python实现：

# 深度优先搜索（DFS）完整示例
# 包含Graph类定义和DFS实现

# 首先定义Graph类（如果还没有定义）
# 定义一个图结构类，支持邻接表存储和有向/无向图
class Graph:
    """图类：使用邻接表实现"""

    # 构造函数，directed决定是否为有向图
    def __init__(self, directed=False):
        """初始化图"""
        # 用字典存储顶点
        self.vertices = {}  # 存储顶点信息
        # 用字典存储每个顶点的邻居（边）
        self.edges = {}     # 存储边信息
        # 是否为有向图
        self.directed = directed

    # 添加顶点方法
    def add_vertex(self, vertex_id, data=None):
        """添加顶点"""
        # 如果该顶点未添加，则加入顶点集合，并初始化边列表
        if vertex_id not in self.vertices:
            self.vertices[vertex_id] = data
            self.edges[vertex_id] = []

    # 添加边的方法
    def add_edge(self, from_vertex, to_vertex, weight=1):
        """添加边"""
        # 如果起点未存在，则先添加起点
        if from_vertex not in self.vertices:
            self.add_vertex(from_vertex)
        # 如果终点未存在，则先添加终点
        if to_vertex not in self.vertices:
            self.add_vertex(to_vertex)

        # 如果边不存在，则添加这条边（起点到终点）
        if (to_vertex, weight) not in self.edges[from_vertex]:
            self.edges[from_vertex].append((to_vertex, weight))

        # 如果是无向图，还需要从终点到起点加一条边
        if not self.directed:
            if (from_vertex, weight) not in self.edges[to_vertex]:
                self.edges[to_vertex].append((from_vertex, weight))

    # 获取指定顶点所有邻居的方法
    def get_neighbors(self, vertex_id):
        """获取某个顶点的所有邻居"""
        # 返回指定顶点的邻居列表
        return self.edges.get(vertex_id, [])


# 深度优先搜索（DFS）实现
# 使用递归方式实现

# 定义递归DFS函数
def dfs_recursive(graph, start_vertex, visited=None, result=None):
    """
    深度优先搜索（递归实现）

    参数：
    - graph: 图对象
    - start_vertex: 起始顶点
    - visited: 已访问的顶点集合（递归时传递）
    - result: 访问结果列表（递归时传递）

    返回：
    - 访问顺序列表
    """
    # 如果是第一次调用，初始化已访问集合
    if visited is None:
        visited = set()

    # 如果是第一次调用，初始化访问结果列表
    if result is None:
        result = []

    # 标记当前顶点为已访问
    visited.add(start_vertex)

    # 把当前顶点放入结果列表
    result.append(start_vertex)

    # 打印正在访问的顶点
    print(f"访问顶点：{start_vertex}")

    # 遍历当前顶点的所有邻居
    neighbors = graph.get_neighbors(start_vertex)
    for neighbor, weight in neighbors:
        # 如果邻居未访问，递归调用DFS
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited, result)

    # 返回所有访问过的顶点顺序
    return result


# 测试DFS
if __name__ == "__main__":
    # 创建一个有向图对象
    graph = Graph(directed=True)

    # 添加顶点A
    graph.add_vertex('A')
    # 添加顶点B
    graph.add_vertex('B')
    # 添加顶点C
    graph.add_vertex('C')
    # 添加顶点D
    graph.add_vertex('D')
    # 添加顶点E
    graph.add_vertex('E')

    # 添加边A->B
    graph.add_edge('A', 'B')
    # 添加边A->C
    graph.add_edge('A', 'C')
    # 添加边B->D
    graph.add_edge('B', 'D')
    # 添加边C->E
    graph.add_edge('C', 'E')
    # 添加边D->E
    graph.add_edge('D', 'E')

    # 打印分隔线
    print("=" * 50)
    # 打印描述文字
    print("深度优先搜索（从A开始）")
    # 再打印一条分隔线
    print("=" * 50)
    # 从顶点A开始执行DFS
    result = dfs_recursive(graph, 'A')
    # 打印最终访问顺序
    print(f"\n访问顺序：{result}")

5.3 广度优先搜索（BFS） #

广度优先搜索（Breadth-First Search, BFS）就像水波扩散，从起始点一层一层向外扩展。

工作原理：

1. 从起始顶点开始，加入队列
2. 从队列中取出一个顶点，访问它
3. 将该顶点的所有未访问邻居加入队列
4. 重复步骤2-3，直到队列为空

实际应用：

• 查找最短路径（无权图）
• 社交网络中的"朋友的朋友"查询
• 网络爬虫

# 导入双端队列，用于实现队列
from collections import deque

# 定义图类（Graph），使用邻接表实现
class Graph:
    """图类：使用邻接表实现"""

    # 构造函数，初始化图，directed表示是否为有向图
    def __init__(self, directed=False):
        # 创建字典存储顶点信息（可以附加顶点数据）
        self.vertices = {}
        # 创建字典存储每个顶点的邻居（边）
        self.edges = {}
        # 指示图是否为有向图
        self.directed = directed

    # 添加顶点的方法
    def add_vertex(self, vertex_id, data=None):
        # 如果顶点不存在，则添加到字典，同时为其创建空的邻接表
        if vertex_id not in self.vertices:
            self.vertices[vertex_id] = data
            self.edges[vertex_id] = []

    # 添加边的方法
    def add_edge(self, from_vertex, to_vertex, weight=1):
        # 如果起始顶点不存在，先添加
        if from_vertex not in self.vertices:
            self.add_vertex(from_vertex)
        # 如果目的顶点不存在，先添加
        if to_vertex not in self.vertices:
            self.add_vertex(to_vertex)
        # 添加边到from_vertex的邻居列表（带权重）
        if (to_vertex, weight) not in self.edges[from_vertex]:
            self.edges[from_vertex].append((to_vertex, weight))
        # 如果是无向图，还需要添加一条反向边
        if not self.directed:
            if (from_vertex, weight) not in self.edges[to_vertex]:
                self.edges[to_vertex].append((from_vertex, weight))

    # 获取某个顶点所有邻居的方法
    def get_neighbors(self, vertex_id):
        # 返回邻接表中的邻居列表
        return self.edges.get(vertex_id, [])

# 定义广度优先搜索（BFS）算法
def bfs(graph, start_vertex):
    """
    广度优先搜索（使用队列实现）

    参数：
    - graph: 图对象
    - start_vertex: 起始顶点

    返回：
    - 访问顺序列表
    """
    # 创建队列，用于存储待访问的顶点
    queue = deque()
    # 创建集合，用于记录已访问顶点，防止重复访问
    visited = set()
    # 创建列表，记录访问顺序
    result = []
    # 将起始顶点加入队列和已访问集合
    queue.append(start_vertex)
    visited.add(start_vertex)
    # 只要队列不为空，就持续遍历
    while queue:
        # 取出队首顶点
        current_vertex = queue.popleft()
        # 记录当前顶点到访问顺序
        result.append(current_vertex)
        # 输出当前访问的顶点
        print(f"访问顶点：{current_vertex}")
        # 遍历当前顶点的所有邻居
        neighbors = graph.get_neighbors(current_vertex)
        for neighbor, weight in neighbors:
            # 如果邻居还未访问，则加入队列和已访问集合
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    # 返回最终访问顺序
    return result

# 测试BFS算法
if __name__ == "__main__":
    # 创建一个有向图实例
    graph = Graph(directed=True)

    # 添加顶点A、B、C、D、E
    graph.add_vertex('A')
    graph.add_vertex('B')
    graph.add_vertex('C')
    graph.add_vertex('D')
    graph.add_vertex('E')

    # 添加边A->B、A->C、B->D、C->E、D->E
    graph.add_edge('A', 'B')
    graph.add_edge('A', 'C')
    graph.add_edge('B', 'D')
    graph.add_edge('C', 'E')
    graph.add_edge('D', 'E')

    # 打印分隔线
    print("=" * 50)
    # 打印算法说明
    print("广度优先搜索（从A开始）")
    # 再打印分隔线
    print("=" * 50)
    # 从顶点A开始执行BFS遍历
    result = bfs(graph, 'A')
    # 打印最后的访问顺序
    print(f"\n访问顺序：{result}")

5.4 DFS vs BFS 对比 #

特性	DFS	BFS
实现方式	递归或栈	队列
访问顺序	深度优先	广度优先
空间复杂度	O(深度)	O(宽度)
适用场景	查找路径、检测环	最短路径、层次遍历
内存使用	较少（递归深度）	较多（队列大小）

6.图与图数据库的关系 #

理解数据结构中的图是学习图数据库的基础。让我们看看它们之间的对应关系。

6.1 概念对应关系 #

数据结构中的图	图数据库中的概念	说明
顶点（Vertex）	节点（Node）	表示实体，如人、商品、概念
边（Edge）	关系（Relationship）	表示实体之间的关系
权重/属性	属性（Property）	存储顶点的数据和边的权重
邻接表/矩阵	存储引擎实现	图数据库内部如何存储数据
图遍历算法	查询语言的基础	Cypher查询就是基于图遍历

6.2 为什么需要图数据库？ #

虽然我们可以用Python实现图，但在实际应用中，我们通常需要图数据库，因为：

1. 数据量大：Python内存有限，无法处理百万、千万级别的数据
2. 持久化存储：数据需要保存到磁盘，程序关闭后不丢失
3. 查询优化：图数据库对图查询进行了专门优化，速度更快
4. 并发支持：多个程序可以同时访问数据库
5. 事务支持：保证数据的一致性

6.3 从图数据结构到图数据库 #

在Python中：

# 创建图
graph = Graph()
graph.add_vertex('A')
graph.add_edge('A', 'B')

在图数据库中（Neo4j）：

// 创建节点
CREATE (a:Person {name: 'A'})

// 创建关系
CREATE (a)-[:KNOWS]->(b:Person {name: 'B'})

两者的概念是相通的，只是实现方式不同！