数据结构与算法 / 系统课时

图的基本概念

图的基本概念

图用于描述对象及其关系。学会区分顶点、边、方向、权重、路径、环与连通分量后,你才能准确阅读图算法,并为后续的广度优先搜索和深度优先搜索选择合适的数据结构。

学习目标

  • 能区分有向图、无向图、加权图与无权图。
  • 能判断路径、简单路径、环、度、入度和出度。
  • 能识别无向图的连通分量,并理解有向图中的可达性。

顶点、边与图的类型

图通常记为 G=(V,E)G=(V,E),其中 VV 是顶点集合,EE 是边集合。顶点表示对象,边表示对象之间的关系。无向边 {u, v} 表示关系没有方向;有向边 (u, v) 表示只能从 u 指向 v。

图的类型 边的含义 典型场景
无向图 关系双向成立 好友关系、双向道路
有向图 关系具有方向 关注关系、任务依赖
加权图 每条边带成本或距离 路线规划、网络延迟
无权图 只关心是否相连 社交连接、网页链接

在无向图中,顶点的度是与它相接的边数。在有向图中,需要分别统计入度和出度:入度表示指向该顶点的边数,出度表示从该顶点发出的边数。

图的类型与基本概念总览

路径、环与连通性

路径是一串顶点序列,相邻顶点之间必须存在对应边。若路径中顶点不重复,称为简单路径;若起点与终点相同,并且至少经过一条边,则形成环。有向图中的路径必须遵循箭头方向。

无向图中,任意两个顶点之间都存在路径时,图是连通图。若整张图不连通,可以把顶点划分为若干连通分量,每个分量内部互相可达,不同分量之间没有路径。有向图还要区分单向可达与强连通,不能直接套用无向图的结论。

邻接表表示

下面用邻接表保存一个无向加权图。图中 A、B、C 构成一个连通分量,D、E 构成另一个连通分量。

python
from collections import deque

def build_graph(vertices, edges):
    graph = {vertex: [] for vertex in vertices}

    # 无向边需要同时写入两个端点的邻接表
    for left, right, weight in edges:
        graph[left].append((right, weight))
        graph[right].append((left, weight))

    for vertex in graph:
        graph[vertex].sort()

    return graph

def connected_components(graph):
    visited = set()
    components = []

    for start in sorted(graph):
        if start in visited:
            continue

        queue = deque([start])
        visited.add(start)
        component = []

        # 从一个未访问顶点出发,收集整个连通分量
        while queue:
            vertex = queue.popleft()
            component.append(vertex)

            for neighbor, _ in graph[vertex]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)

        components.append(component)

    return components

def main():
    vertices = ["A", "B", "C", "D", "E"]
    edges = [
        ("A", "B", 2),
        ("B", "C", 1),
        ("D", "E", 3),
    ]

    graph = build_graph(vertices, edges)

    print("邻接表:")
    for vertex in sorted(graph):
        neighbors = ", ".join(
            f"{neighbor}({weight})" for neighbor, weight in graph[vertex]
        )
        print(f"{vertex}: {neighbors}")

    print("度数:")
    for vertex in sorted(graph):
        print(f"{vertex}: {len(graph[vertex])}")

    print(f"连通分量: {connected_components(graph)}")

if __name__ == "__main__":
    main()

运行命令如下:

bash
python graph_basics.py

预期输出

text
邻接表:
A: B(2)
B: A(2), C(1)
C: B(1)
D: E(3)
E: D(3)
度数:
A: 1
B: 2
C: 1
D: 1
E: 1
连通分量: [['A', 'B', 'C'], ['D', 'E']]

易混淆点与练习

边数与度数不能直接混为一谈。无向图中,所有顶点度数之和等于边数的 2 倍;有向图中,所有顶点入度之和与出度之和都等于边数。路径也不等于简单路径,因为普通路径允许重复经过顶点或边。

练习 1:在示例图中增加边 C-D,预测连通分量数量和各顶点度数,再运行程序验证。

练习 2:把示例改成有向图,只把边写入起点的邻接表,并分别统计每个顶点的入度与出度。验收条件是输出的入度总和、出度总和都等于边数。

本课总结

  • 图由顶点集合和边集合组成,方向与权重决定了边的语义。
  • 路径、环、度和连通分量是描述图结构与可达性的基础概念。
  • 邻接表适合表示稀疏图,也是后续 BFS 和 DFS 的常用存储结构。

下一课预告

下一阶段将学习图的具体表示方式,并比较邻接表与邻接矩阵在空间占用、查边效率和遍历方式上的差异。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

图的基本概念

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通