图的表示与存储

数据结构与算法专题 · 邻接矩阵与邻接表详解

专题：数据结构与算法系统学习

关键词：数据结构, 算法, 图, 邻接矩阵, 邻接表, 有向图, 无向图, 加权图, 度

一、图的定义与基本术语

图（Graph）是一种非线性数据结构，由顶点（Vertex）的有限集合和边（Edge）的有限集合组成。图是计算机科学中最重要的抽象模型之一，广泛用于表示实体之间的复杂关系——社交网络中的好友关系、地图中的道路连接、网页之间的超链接、神经网络中的神经元连接，都可以用图来建模。

图的正式数学定义为 G = (V, E)，其中 V 是顶点的非空有限集合，E 是边的有限集合，每条边是顶点集合 V 中两个顶点的无序对或有序对。根据边是否有方向、是否附带权重，图可以划分为多种类型。

1.1 图的分类

无向图（Undirected Graph）：边没有方向，即 (u, v) 与 (v, u) 表示同一条边。在无向图中，顶点之间的连线不带箭头，表示双向关系。例如，微信好友关系就是无向图——A是B的好友，B也一定是A的好友。

有向图（Directed Graph）：边有方向，用 <u, v> 表示从 u 指向 v 的一条弧。有向图中的两条弧 <u, v> 和 <v, u> 是不同的。微博的关注关系就是有向图——A关注B不代表B关注A。

加权图（Weighted Graph）：在边的基础上附加了权值（Weight），权值可以表示距离、成本、时间、容量等。地图导航中两点之间的行驶距离就是典型的加权图应用。

稀疏图 vs 稠密图：这是从边的密度角度进行的划分。设图有 V 个顶点、E 条边，完全图的边数为 V(V-1)/2（无向）或 V(V-1)（有向）。当 E 远小于 V² 时称为稀疏图，当 E 接近 V² 时称为稠密图。这一分类直接影响存储方式的选择。

1.2 基本术语

顶点（Vertex）：图中的基本元素，也称为结点（Node）。通常用 V = {v₁, v₂, ..., vₙ} 表示。
边（Edge）：顶点之间的连线，表示两个顶点之间存在某种关系。
度（Degree）：与顶点相关联的边的数目。无向图中顶点 v 的度记作 deg(v)。
入度（In-Degree）：有向图中，以顶点 v 为终点的弧的数目，记作 indeg(v)。
出度（Out-Degree）：有向图中，以顶点 v 为起点的弧的数目，记作 outdeg(v)。
路径（Path）：从顶点 u 到顶点 v 经过的顶点序列。路径的长度是路径上边的数目。
连通（Connected）：无向图中，如果顶点 u 到 v 存在路径，则称 u 和 v 是连通的。
连通分量（Connected Component）：无向图中的极大连通子图。一个非连通图包含多个连通分量。
强连通（Strongly Connected）：有向图中，如果顶点 u 到 v 和 v 到 u 都存在路径，则称 u 和 v 是强连通的。
自环（Self-Loop）：连接顶点到自身的边。简单图一般不考虑自环。
多重边（Parallel Edge）：两个顶点之间有多条边的现象。不含多重边的图称为简单图。

理解要点：图的本质是"顶点+关系"。与线性表（一对一）和树（一对多）不同，图是多对多的关系结构，任何两个顶点之间都可能存在关系。这也使得图的表示和存储比线性表和树更加复杂和多样化。

1.3 Python 中图的基本抽象

在 Python 中，我们可以先定义一个基础图类来理解图的核心要素：

class Graph:
    """图的抽象基类 - 定义图的核心接口"""

    def __init__(self, vertices=None):
        self._vertices = set()
        self._edge_count = 0
        if vertices:
            self._vertices.update(vertices)

    def add_vertex(self, v):
        raise NotImplementedError

    def add_edge(self, u, v, weight=1):
        raise NotImplementedError

    def remove_edge(self, u, v):
        raise NotImplementedError

    def has_edge(self, u, v):
        raise NotImplementedError

    def neighbors(self, v):
        raise NotImplementedError

    def degree(self, v):
        raise NotImplementedError

    def __repr__(self):
        return f"Graph(vertices={len(self._vertices)}, edges={self._edge_count})"

这个抽象基类定义了图的核心操作：添加顶点、添加边、删除边、判断边是否存在、获取邻居顶点、计算度数。不同存储方式（邻接矩阵、邻接表）将用不同的方式实现这些接口。

二、邻接矩阵（Adjacency Matrix）

邻接矩阵是图的最直观的存储方式。它使用一个 V x V 的二维矩阵（通常用二维列表实现）来表示图中顶点之间的邻接关系。假设图有 V 个顶点，编号为 0, 1, 2, ..., V-1，则矩阵 A 的元素定义如下：

无权图：A[i][j] = 1 表示顶点 i 到 j 存在边，A[i][j] = 0 表示不存在边。
加权图：A[i][j] = w 表示顶点 i 到 j 存在权重为 w 的边，A[i][j] = ∞（或 None）表示不存在边。
无向图的邻接矩阵是对称矩阵，因为 (u, v) 和 (v, u) 是同一条边，所以 A[i][j] = A[j][i]。
有向图的邻接矩阵不一定对称，A[i][j] 和 A[j][i] 可以不同。

2.1 邻接矩阵的 Python 实现

下面给出一个完整的邻接矩阵实现，支持无向图/有向图、加权图/无权图：

class AdjMatrixGraph:
    """邻接矩阵实现的图

    空间复杂度: O(V²)
    判断边存在: O(1)
    获取所有邻居: O(V)
    添加/删除边: O(1)
    """

    def __init__(self, num_vertices, directed=False, weighted=False):
        self._V = num_vertices
        self._E = 0
        self._directed = directed
        self._weighted = weighted

        # 初始化 V x V 矩阵，全部填充为 0 或 INF
        if weighted:
            self._INF = float('inf')
            self._matrix = [[self._INF for _ in range(num_vertices)]
                            for _ in range(num_vertices)]
            # 对角线设为 0（顶点到自身距离为0）
            for i in range(num_vertices):
                self._matrix[i][i] = 0
        else:
            self._matrix = [[0 for _ in range(num_vertices)]
                            for _ in range(num_vertices)]

    def add_edge(self, u, v, weight=1):
        """添加一条从 u 到 v 的边"""
        if self._weighted:
            self._matrix[u][v] = weight
        else:
            self._matrix[u][v] = 1

        if not self._directed:
            # 无向图需要对称添加
            if self._weighted:
                self._matrix[v][u] = weight
            else:
                self._matrix[v][u] = 1

        self._E += 1

    def has_edge(self, u, v):
        """判断边 (u,v) 是否存在 — O(1) 时间复杂度"""
        if self._weighted:
            return self._matrix[u][v] != self._INF and u != v
        return self._matrix[u][v] != 0

    def get_weight(self, u, v):
        """获取边的权重"""
        return self._matrix[u][v]

    def neighbors(self, v):
        """获取顶点 v 的所有邻接顶点 — O(V) 需遍历整行"""
        result = []
        for i in range(self._V):
            if self._weighted:
                if self._matrix[v][i] != self._INF and v != i:
                    result.append(i)
            else:
                if self._matrix[v][i] != 0:
                    result.append(i)
        return result

    def degree(self, v):
        """计算顶点 v 的度"""
        return len(self.neighbors(v))

    def display(self):
        """打印邻接矩阵"""
        for i in range(self._V):
            row = []
            for j in range(self._V):
                val = self._matrix[i][j]
                if val == self._INF:
                    row.append('∞')
                else:
                    row.append(str(val))
            print(' '.join(row))

    def __repr__(self):
        return (f"AdjMatrixGraph(V={self._V}, E={self._E}, "
                f"directed={self._directed}, weighted={self._weighted})")

2.2 邻接矩阵的使用示例

以下示例演示了如何使用邻接矩阵构建和操作一个无向无权图：

# 创建一个无向无权图（4个顶点）
g = AdjMatrixGraph(num_vertices=4, directed=False, weighted=False)

# 添加边
g.add_edge(0, 1)   # A-B
g.add_edge(0, 2)   # A-C
g.add_edge(1, 2)   # B-C
g.add_edge(2, 3)   # C-D

# 检查边 (0,1) 是否存在 — O(1)
print(g.has_edge(0, 1))  # True

# 获取顶点 2 的邻居
print(g.neighbors(2))     # [0, 1, 3]

# 打印邻接矩阵
g.display()
# 输出:   0 1 1 0
#         1 0 1 0
#         1 1 0 1
#         0 0 1 0

# 创建有向加权图
dg = AdjMatrixGraph(num_vertices=3, directed=True, weighted=True)
dg.add_edge(0, 1, 5)   # 0 → 1, 权重 5
dg.add_edge(0, 2, 3)   # 0 → 2, 权重 3
dg.add_edge(1, 2, 2)   # 1 → 2, 权重 2
dg.display()
# 输出:   0 5 3
#         ∞ 0 2
#         ∞ ∞ 0

2.3 邻接矩阵的复杂度分析

空间复杂度：O(V²)。无论实际有多少条边，矩阵都需要 V² 个存储单元。对于稀疏图来说，这会造成极大的空间浪费。例如一个拥有 10,000 个顶点的稀疏图，仅邻接矩阵就需要约 100MB 的存储空间（假设每个元素 1 字节），而实际边数可能只有几万条。

时间复杂度：判断边是否存在为 O(1)，添加/删除边也是 O(1)，但获取某个顶点的所有邻接点需要 O(V) 时间（必须遍历一行）。

适用场景：稠密图（E 接近 V²）或需要频繁判断边是否存在的算法（如 Floyd-Warshall 全源最短路径算法）。

三、邻接表（Adjacency List）

邻接表是另一种主流存储方式，它用 V 个链表（或动态数组）来存储每个顶点的邻接顶点。对于每个顶点 v，邻接表维护一个列表，存储所有与 v 直接相连的顶点及其边权重。

邻接表克服了邻接矩阵空间浪费的缺点，存储量与顶点数和边数成正比，是稀疏图的首选存储方式。在 Python 中，通常使用字典 + 集合或字典 + 列表的组合来实现邻接表。

3.1 邻接表的 Python 实现（字典+集合版本）

class AdjListGraph:
    """基于字典+集合的邻接表实现（无权图）

    空间复杂度: O(V + E)
    判断边存在: O(deg(v)) 平均 O(1)（哈希集合）
    获取所有邻居: O(deg(v))
    添加边: O(1) 平均
    """

    def __init__(self, directed=False):
        self._graph = {}    # {vertex: set(neighbors)}
        self._E = 0
        self._directed = directed

    def add_vertex(self, v):
        """添加顶点"""
        if v not in self._graph:
            self._graph[v] = set()

    def add_edge(self, u, v):
        """添加一条从 u 到 v 的无权边"""
        self.add_vertex(u)
        self.add_vertex(v)
        self._graph[u].add(v)
        if not self._directed:
            self._graph[v].add(u)
        self._E += 1

    def has_edge(self, u, v):
        """判断边 (u, v) 是否存在"""
        return v in self._graph.get(u, set())

    def neighbors(self, v):
        """获取顶点 v 的所有邻居"""
        return self._graph.get(v, set())

    def degree(self, v):
        """计算顶点 v 的度"""
        return len(self.neighbors(v))

    def remove_edge(self, u, v):
        """删除边 (u, v)"""
        if u in self._graph and v in self._graph[u]:
            self._graph[u].discard(v)
            if not self._directed:
                self._graph[v].discard(u)
            self._E -= 1

    def vertices(self):
        """返回所有顶点"""
        return list(self._graph.keys())

    def edge_count(self):
        return self._E

    def vertex_count(self):
        return len(self._graph)

    def display(self):
        for v, neighbors in self._graph.items():
            print(f"{v} → {neighbors}")

3.2 邻接表的加权图版本（字典+字典）

class WeightedAdjListGraph:
    """基于字典+字典的邻接表实现（加权图）

    对于加权图，使用 {neighbor: weight} 字典
    代替 {neighbor} 集合
    """

    def __init__(self, directed=False):
        self._graph = {}    # {vertex: {neighbor: weight}}
        self._E = 0
        self._directed = directed

    def add_vertex(self, v):
        if v not in self._graph:
            self._graph[v] = {}

    def add_edge(self, u, v, weight=1):
        self.add_vertex(u)
        self.add_vertex(v)
        self._graph[u][v] = weight
        if not self._directed:
            self._graph[v][u] = weight
        self._E += 1

    def has_edge(self, u, v):
        return v in self._graph.get(u, {})

    def get_weight(self, u, v):
        """获取边 (u, v) 的权重"""
        return self._graph.get(u, {}).get(v, None)

    def neighbors(self, v):
        """获取顶点 v 的邻居及其权重：返回 dict {neighbor: weight}"""
        return self._graph.get(v, {})

    def degree(self, v):
        return len(self.neighbors(v))

    def display(self):
        for v, nbrs in self._graph.items():
            edges = ', '.join(f"{n}({w})" for n, w in nbrs.items())
            print(f"{v} → {edges}")

3.3 邻接表使用示例

# 示例1：无向无权图 - 社交网络
social = AdjListGraph(directed=False)
social.add_edge('Alice', 'Bob')
social.add_edge('Alice', 'Charlie')
social.add_edge('Bob', 'David')
social.add_edge('Charlie', 'Eve')
social.display()
# Alice → {'Charlie', 'Bob'}
# Bob → {'Alice', 'David'}
# Charlie → {'Alice', 'Eve'}
# David → {'Bob'}
# Eve → {'Charlie'}

# 示例2：有向加权图 - 城市之间航班
flights = WeightedAdjListGraph(directed=True)
flights.add_edge('北京', '上海', 1200)
flights.add_edge('北京', '广州', 1800)
flights.add_edge('上海', '深圳', 1400)
flights.add_edge('广州', '深圳', 200)
print(flights.get_weight('北京', '上海'))  # 1200
print(flights.degree('北京'))  # 出度 = 2
flights.display()
# 北京 → 上海(1200), 广州(1800)
# 上海 → 深圳(1400)
# 广州 → 深圳(200)
# 深圳 → 

3.4 邻接表的复杂度分析

空间复杂度：O(V + E)。对于稀疏图来说非常高效。无向图每条边存储两次（两个方向各一次），有向图每条边存储一次。存储结构与实际边数成正比，没有浪费。

时间复杂度：判断边是否存在需要遍历邻接链表（Python 集合实现下平均 O(1)），获取邻居需 O(deg(v))，添加顶点/边为 O(1) 摊还。

适用场景：稀疏图（绝大多数实际问题中的图都是稀疏的），需要频繁遍历邻居的算法（如 DFS、BFS、Dijkstra 等）。

四、邻接矩阵 vs 邻接表对比

两种存储方式各有优劣，选择哪种取决于具体的应用场景、图的密度和需要执行的操作。下面从多个维度进行全面对比。

4.1 对比表格

对比维度	邻接矩阵	邻接表
空间复杂度	O(V²) — 固定开销	O(V + E) — 与边数成正比
判断边 (u,v)	O(1) — 直接访问矩阵元素	O(deg(u)) 或 O(1)（哈希表）
获取所有邻居	O(V) — 必须遍历整行	O(deg(v)) — 直接返回列表
添加边	O(1)	O(1) 平均
删除边	O(1)	O(deg(u)) 或 O(1)（哈希表）
添加顶点	O(V²) — 需重建整个矩阵	O(1)
遍历全图	O(V²)	O(V + E)
实现难度	简单直观	中等，需管理链表/集合
适合图类型	稠密图	稀疏图
缓存友好性	好（连续内存，空间局部性）	差（离散内存，指针跳跃）

4.2 什么时候用邻接矩阵？

图非常稠密，E 接近 V²。此时邻接矩阵的空间利用率高，且判断边的时间只需 O(1)。
需要频繁判断任意两个顶点之间是否存在边，例如 Floyd-Warshall 全源最短路径算法反复查询边的权重。
顶点数量较少（几千以内），且图结构在初始化后不会频繁增减顶点。
需要利用矩阵运算进行图分析（如 PageRank 的幂迭代法可用矩阵乘法加速）。

4.3 什么时候用邻接表？

图比较稀疏（大多数实际应用），E 远小于 V²。
需要频繁遍历邻居顶点，例如 BFS、DFS、Dijkstra、拓扑排序等图算法。
图结构动态变化，经常需要添加或删除顶点。
顶点数量特别大（几万到上百万），邻接矩阵的内存无法承受。

经验法则：当 E < V · log(V) 时，邻接表通常更优；当 E > V²/4 时，邻接矩阵可能更合适。中间地带需结合具体操作场景分析。在实际工程中，邻接表是默认选择，因为大多数真实世界的图都是稀疏的。

五、图的度计算

度是图论中最基础的统计量之一，在算法分析、网络分析中有着重要作用。下面分别讨论无向图和有向图中度的计算方法。

5.1 无向图的度

在无向图中，顶点 v 的度等于与其相连的边的数目。对于邻接表存储，度就是邻接表的长度；对于邻接矩阵存储，度就是该行（或该列）中非零元素的个数。

重要性质：所有顶点的度之和等于边数的两倍，即 Σdeg(v) = 2E。这是因为每条边贡献了两个度（为两个端点各增加一度）。这一性质在检测图的连通性和判断图是否为欧拉图时非常有用。

def degree_distribution(graph):
    """计算图的度分布"""
    degrees = {}
    for v in graph.vertices():
        d = graph.degree(v)
        degrees[d] = degrees.get(d, 0) + 1
    return degrees

# 验证 Σdeg(v) = 2E
def verify_handshaking(graph):
    total_degree = sum(graph.degree(v) for v in graph.vertices())
    return total_degree == 2 * graph.edge_count()

# 使用
g = AdjListGraph(directed=False)
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('B', 'C')
g.add_edge('C', 'D')
for v in g.vertices():
    print(f"deg({v}) = {g.degree(v)}")
# deg(A) = 2, deg(B) = 2, deg(C) = 3, deg(D) = 1
print(verify_handshaking(g))  # True (2+2+3+1 == 2*4)

5.2 有向图的入度和出度

在有向图中，度分为入度和出度。入度是指向该顶点的边数（别人指向自己的弧），出度是从该顶点发出的边数。对于邻接表存储，出度就是当前顶点的邻接表长度，入度需要额外维护一个反向邻接表或遍历所有顶点进行统计。

class DirectedGraph(AdjListGraph):
    """有向图 - 额外支持入度计算"""

    def __init__(self):
        super().__init__(directed=True)
        self._in_degree = {}   # {vertex: count}

    def add_edge(self, u, v):
        super().add_edge(u, v)
        # 维护入度表
        self._in_degree[v] = self._in_degree.get(v, 0) + 1
        if u not in self._in_degree:
            self._in_degree[u] = self._in_degree.get(u, 0)

    def in_degree(self, v):
        """返回顶点 v 的入度"""
        return self._in_degree.get(v, 0)

    def out_degree(self, v):
        """返回顶点 v 的出度"""
        return self.degree(v)

    def sources(self):
        """返回所有入度为 0 的顶点（源点）"""
        return [v for v in self.vertices()
                if self.in_degree(v) == 0]

    def sinks(self):
        """返回所有出度为 0 的顶点（汇点）"""
        return [v for v in self.vertices()
                if self.out_degree(v) == 0]

    def is_balanced(self, v):
        """判断顶点 v 的出度和入度是否相等（用于欧拉路径判断）"""
        return self.in_degree(v) == self.out_degree(v)

# 示例：课程先修关系
courses = DirectedGraph()
courses.add_edge('数据结构', '算法设计')
courses.add_edge('高等数学', '概率论')
courses.add_edge('高等数学', '线性代数')
courses.add_edge('线性代数', '数据结构')
courses.add_edge('概率论', '机器学习')
courses.add_edge('算法设计', '机器学习')

print(f"'机器学习'入度={courses.in_degree('机器学习')}")   # 2
print(f"'高等数学'出度={courses.out_degree('高等数学')}")  # 2
print(f"源点（无先修课程）: {courses.sources()}")         # ['高等数学']

六、图的 Python 表示（经典模式总结）

在实际的 Python 编程中，图的表示有多种方式，取决于问题的规模和需求。以下是几种最常用的模式。

6.1 字典 + 集合（最常用、最简洁）

对于无权图，特别是算法竞赛和面试中，字典+集合是最常见的做法。简洁、高效、易于使用。

# 标准模式：{vertex: set(neighbors)}
graph = {
    'A': {'B', 'C'},
    'B': {'A', 'D'},
    'C': {'A', 'E'},
    'D': {'B'},
    'E': {'C'},
}

# BFS 遍历示例
from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        node = queue.popleft()
        print(node, end=' ')
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

bfs(graph, 'A')  # A B C D E

6.2 字典 + 字典（加权图）

# 加权图：{vertex: {neighbor: weight}}
weighted_graph = {
    'A': {'B': 5, 'C': 3},
    'B': {'A': 5, 'D': 2},
    'C': {'A': 3, 'E': 4},
    'D': {'B': 2, 'E': 1},
    'E': {'C': 4, 'D': 1},
}

# Dijkstra 最短路径（简化版）
import heapq

def dijkstra(graph, start):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    pq = [(0, start)]

    while pq:
        d, node = heapq.heappop(pq)
        if d > dist[node]:
            continue
        for nbr, w in graph[node].items():
            nd = d + w
            if nd < dist[nbr]:
                dist[nbr] = nd
                heapq.heappush(pq, (nd, nbr))
    return dist

print(dijkstra(weighted_graph, 'A'))
# {'A': 0, 'B': 5, 'C': 3, 'D': 7, 'E': 7}

6.3 邻接列表（顶点编号版）

当顶点使用整数编号时，可以用列表代替字典，性能更好：

# 顶点编号为 0..n-1，使用列表的列表
n = 5
graph = [[] for _ in range(n)]

# 添加边 (0-1, 0-2, 1-3, 2-4)
edges = [(0, 1), (0, 2), (1, 3), (2, 4)]
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)   # 无向图

# DFS 遍历
def dfs(graph, start):
    visited = [False] * len(graph)
    def _dfs(v):
        visited[v] = True
        print(v, end=' ')
        for nbr in graph[v]:
            if not visited[nbr]:
                _dfs(nbr)
    _dfs(start)

dfs(graph, 0)  # 0 1 3 2 4

6.4 类封装（面向对象方式）

在较大的项目中，使用类封装图结构是更好的实践：

class Graph:
    """完整的图类封装 - 支持动态增删改查"""

    def __init__(self, directed=False):
        self._adj = {}         # 邻接表 {vertex: {neighbor: weight}}
        self._directed = directed
        self._edge_count = 0

    @property
    def vertices(self):
        return list(self._adj.keys())

    @property
    def edges(self):
        """返回所有边的列表 [(u, v, w), ...]"""
        result = []
        for u in self._adj:
            for v, w in self._adj[u].items():
                if self._directed or u < v:
                    result.append((u, v, w))
        return result

    def add_vertex(self, v):
        if v not in self._adj:
            self._adj[v] = {}

    def add_edge(self, u, v, weight=1):
        self.add_vertex(u)
        self.add_vertex(v)
        self._adj[u][v] = weight
        if not self._directed:
            self._adj[v][u] = weight
        self._edge_count += 1

    def remove_edge(self, u, v):
        if u in self._adj and v in self._adj[u]:
            del self._adj[u][v]
            if not self._directed:
                del self._adj[v][u]
            self._edge_count -= 1

    def has_edge(self, u, v):
        return u in self._adj and v in self._adj[u]

    def neighbors(self, v):
        return self._adj.get(v, {})

    def degree(self, v):
        return len(self._adj.get(v, {}))

    def __len__(self):
        return len(self._adj)

    def __repr__(self):
        return (f"Graph(V={len(self._adj)}, E={self._edge_count}, "
                f"directed={self._directed})")

七、加权图的表示

加权图（Weighted Graph）是图论和实际应用中最常见的图类型之一。在加权图中，每条边都附带一个数值（权值），用于表示距离、成本、时间、容量、概率等度量。

7.1 加权图的存储方式

加权图可以用邻接矩阵或邻接表存储，但需要额外保存权重信息：

邻接矩阵：A[i][j] = weight（权重值），不存在的边用 INF 或 None 表示。
邻接表（字典+字典）：graph[u] = {v₁: w₁, v₂: w₂, ...}，每个邻居映射到对应的权重。
边列表：[(u₁, v₁, w₁), (u₂, v₂, w₂), ...]，适合 Kruskal 等需要按权重排序的算法。

7.2 加权图的应用场景

# 场景1：地图导航（顶点=城市，权重=距离）
road_network = {
    '北京': {'天津': 120, '石家庄': 270, '济南': 410},
    '天津': {'北京': 120, '济南': 320},
    '石家庄': {'北京': 270, '郑州': 420},
    '济南': {'北京': 410, '天津': 320, '南京': 620},
    '郑州': {'石家庄': 420, '南京': 680},
    '南京': {'济南': 620, '郑州': 680},
}

# 场景2：任务调度图（顶点=任务，权重=执行时间）
# 关键路径法（CPM）中的加权有向无环图
task_graph = {
    'T1': {'T2': 3, 'T3': 5},    # T1完成后可执行T2（耗时3天）和T3（5天）
    'T2': {'T4': 2},
    'T3': {'T4': 4, 'T5': 3},
    'T4': {'T6': 1},
    'T5': {'T6': 2},
    'T6': {},
}

# 场景3：概率图模型（权重=概率）
# 马尔可夫链的状态转移图
markov_chain = {
    '晴天': {'晴天': 0.8, '阴天': 0.15, '雨天': 0.05},
    '阴天': {'晴天': 0.3, '阴天': 0.5, '雨天': 0.2},
    '雨天': {'晴天': 0.2, '阴天': 0.3, '雨天': 0.5},
}

7.3 边列表与邻接表的相互转换

不同的图算法对输入格式有不同要求。例如 Kruskal 算法需要边列表（并按权重排序），而 BFS/DFS 需要邻接表。因此，掌握两者之间的转换非常有用。

def edge_list_to_adjacency(edges, directed=False):
    """边列表 → 邻接表

    Args:
        edges: [(u, v, w), ...]
        directed: 是否为有向图
    Returns:
        {vertex: {neighbor: weight}}
    """
    graph = {}
    for u, v, w in edges:
        graph.setdefault(u, {})[v] = w
        if not directed:
            graph.setdefault(v, {})[u] = w
        # 确保孤立顶点也在字典中
        graph.setdefault(v, {})  # 仅在 directed=True 时需要
    return graph

def adjacency_to_edge_list(graph, directed=False):
    """邻接表 → 边列表"""
    edges = []
    seen = set()
    for u in graph:
        for v, w in graph[u].items():
            if directed:
                edges.append((u, v, w))
            elif (u, v) not in seen:
                edges.append((u, v, w))
                seen.add((u, v))
                seen.add((v, u))
    return edges

# 示例
edge_list = [
    ('A', 'B', 5),
    ('A', 'C', 3),
    ('B', 'D', 2),
    ('C', 'D', 4),
]
g = edge_list_to_adjacency(edge_list)
print(g)
# {'A': {'B': 5, 'C': 3}, 'B': {'A': 5, 'D': 2}, 
#  'C': {'A': 3, 'D': 4}, 'D': {'B': 2, 'C': 4}}

# Kruskal 算法需要按权重排序的边列表
sorted_edges = sorted(edge_list, key=lambda x: x[2])
print(sorted_edges)
# [('A', 'B', 2), ('A', 'C', 3), ('B', 'D', 4), ('C', 'D', 5)]

八、NetworkX 库基础

NetworkX 是 Python 生态中最流行的图论与网络分析库，提供了丰富的图数据结构和分析算法。在实际项目中，除非有特殊需求，否则直接使用 NetworkX 通常比手写图类更高效、更可靠。

8.1 基本使用

import networkx as nx

# 创建不同类型的图
G = nx.Graph()          # 无向图（默认）
DG = nx.DiGraph()       # 有向图
WG = nx.Graph()         # 加权图（仍用 Graph，在边上加 weight 属性）

# 添加节点
G.add_node('A')
G.add_nodes_from(['B', 'C', 'D'])

# 添加边
G.add_edge('A', 'B')
G.add_edges_from([('A', 'C'), ('B', 'D'), ('C', 'D')])

# 加权边
WG.add_weighted_edges_from([
    ('A', 'B', 5.0),
    ('A', 'C', 3.0),
    ('B', 'C', 2.5),
])

# 基本信息
print(G)                          # Graph with 4 nodes and 4 edges
print(G.number_of_nodes())       # 4
print(G.number_of_edges())       # 4
print(list(G.neighbors('A')))   # ['B', 'C']
print(G.degree['D'])             # 2

8.2 内置图算法

# 最短路径
path = nx.shortest_path(G, source='A', target='D')
print(path)                      # ['A', 'C', 'D']（或其他最短路径）

length = nx.shortest_path_length(G, source='A', target='D')
print(length)                    # 2

# 连通分量
components = list(nx.connected_components(G))
print(components)                # [{'A', 'B', 'C', 'D'}]

# 最小生成树
mst = nx.minimum_spanning_tree(WG)
print(mst.edges(data=True))
# [('A', 'C', {'weight': 3.0}), ('B', 'C', {'weight': 2.5}), ('A', 'B', {'weight': 5.0})]

# 中心性分析
centrality = nx.degree_centrality(G)
print(centrality)                # {'A': 0.5, 'B': 0.5, 'C': 0.5, 'D': 0.5}

# PageRank 算法
# 创建一个有向图来演示
DG.add_edges_from([
    ('A', 'B'), ('A', 'C'),
    ('B', 'C'), ('C', 'A'),
    ('D', 'C'),
])
pagerank = nx.pagerank(DG)
for node, score in sorted(pagerank.items(), key=lambda x: x[1], reverse=True):
    print(f"  {node}: {score:.3f}")
# 输出示例:
#   C: 0.396
#   A: 0.346
#   B: 0.205
#   D: 0.053

8.3 可视化

import matplotlib.pyplot as plt

# 创建示例图
G = nx.karate_club_graph()  # 经典的空手道俱乐部图

# 基本绘制
pos = nx.spring_layout(G, seed=42)  # 布局算法
plt.figure(figsize=(10, 8))
nx.draw(G, pos, with_labels=True,
        node_color='lightblue',
        node_size=500,
        font_size=10,
        font_weight='bold',
        edge_color='gray')
plt.title('Zachary Karate Club Graph')
plt.axis('off')
plt.show()

# 按社区着色
communities = nx.community.greedy_modularity_communities(G)
colors = ['#1f78b4', '#33a02c', '#e31a1c', '#ff7f00']
node_colors = ['gray'] * G.number_of_nodes()
for i, comm in enumerate(communities):
    for node in comm:
        node_colors[node] = colors[i]

plt.figure(figsize=(10, 8))
nx.draw(G, pos, with_labels=True,
        node_color=node_colors,
        node_size=500,
        font_size=10,
        edge_color='gray',
        cmap=plt.cm.Set1)
plt.title('Karate Club - Community Detection')
plt.axis('off')
plt.show()

提示：NetworkX 提供了超过 100 种图算法，包括最短路径、连通性、社区发现、中心性分析、图同构、最大流等。官方文档（networkx.org）是最佳学习资源。在工程实践中，优先使用 NetworkX 而非自建轮子，除非有特殊的性能或定制需求。

九、核心要点总结

1. 图的本质：图 = 顶点集 V + 边集 E，是描述多对多关系的通用数据结构。

2. 两种存储方式：邻接矩阵（O(V²)空间，O(1)查询，适合稠密图）和邻接表（O(V+E)空间，适合稀疏图）。

3. 存储选择原则：稠密图用邻接矩阵，稀疏图用邻接表；频繁查边用矩阵，频繁遍历邻居用邻接表。

4. 有向图度分析：出度 + 入度 = 总关联边数。入度为零的顶点为源点，出度为零的为汇点。

5. Python 最佳实践：无权图用字典+集合，加权图用字典+字典，整数编号顶点用列表的列表。

6. 加权图关键：权重存储是扩展点。边列表格式便于 Kruskal 排序，邻接表格式便于 Dijkstra 遍历。

7. NetworkX：生产环境首选，内置数十种图算法和分析工具，大幅降低开发成本。

十、进一步思考与练习

练习1：实现一个邻接表到邻接矩阵的转换函数，分析其时间复杂度和空间复杂度。

练习2：给定一个包含 100 万个顶点、200 万条边的社交网络图，应该选择哪种存储方式？为什么？

练习3：设计一个支持动态增删顶点和边的图类，比较不同实现的性能差异。

练习4：使用 NetworkX 加载一个真实数据集（如 Facebook 社交网络或航班网络），计算节点的度分布并绘制直方图。

练习5：实现一个函数，检测给定图是否为树（无环连通图），要求时间复杂度 O(V+E)。

"图是计算机科学中最优雅、最通用的抽象之一。掌握了图的表示与存储，就掌握了解决复杂关系问题的基础工具。" — 数据结构与算法学习笔记