图论基础概念

What · 是什么

图(Graph)是一个二元组 G=(V,E)，其中 V 是非空点集，E 是连接点与点之间边的集合。图分为无向图(undirected graph)、有向图(directed graph)和混合图。若每条边有权则称为赋权图。图论基础概念包括：度(degree)、路径(path)、环(cycle)、连通性(connectivity)、子图(subgraph)、简单图(simple graph)等，是所有图论算法的基石。

Why · 为什么

How · 实现

伪代码

# 图的Python表示(邻接表)
adj = [[] for _ in range(n)]
for u, v in edges:
    adj[u].append(v)    # 有向图
    # adj[v].append(u)  # 无向图

# 度数计算
deg = [len(adj[u]) for u in range(n)]  # 出度(有向图)

# 检查路径(简化版)
visited = [False]*n
def dfs(u, target):
    if u == target: return True
    visited[u] = True
    for v in adj[u]:
        if not visited[v] and dfs(v, target):
            return True
    return False

Python 实现

from collections import defaultdict, deque


class Graph:
    """简单图基础类: 支持有向/无向, 邻接表存储
    提供度数计算、连通块计数、环检测等基础操作
    """
    def __init__(self, n, directed=False):
        self.n = n
        self.directed = directed
        self.adj = defaultdict(list)

    def add_edge(self, u, v):
        self.adj[u].append(v)
        if not self.directed:
            self.adj[v].append(u)

    def degree(self, u):
        """返回节点 u 的度(无向)或出度(有向)"""
        return len(self.adj[u])

    def in_degree(self, u):
        """返回节点 u 的入度(仅对有向图有意义)"""
        cnt = 0
        for v in range(self.n):
            for w in self.adj[v]:
                if w == u:
                    cnt += 1
        return cnt

    def connected_components(self):
        """求无向图连通块数量 (BFS)"""
        visited = [False] * self.n
        count = 0
        for start in range(self.n):
            if not visited[start]:
                count += 1
                q = deque([start])
                visited[start] = True
                while q:
                    u = q.popleft()
                    for v in self.adj[u]:
                        if not visited[v]:
                            visited[v] = True
                            q.append(v)
        return count

    def has_path(self, s, t):
        """检查 s 到 t 是否存在路径 (BFS)"""
        visited = [False] * self.n
        q = deque([s])
        visited[s] = True
        while q:
            u = q.popleft()
            if u == t:
                return True
            for v in self.adj[u]:
                if not visited[v]:
                    visited[v] = True
                    q.append(v)
        return False

    def handshake_check(self):
        """验证握手定理: sum(deg) == 2*|E| (无向图)"""
        total = sum(self.degree(u) for u in range(self.n))
        edge_count = sum(len(self.adj[u]) for u in range(self.n))
        if not self.directed:
            return total == 2 * edge_count // 2 * 2 and total == edge_count
        return total == edge_count  # 有向图 sum(out) = |E|


if __name__ == "__main__":
    # 无向图: 0-1, 1-2, 3-4 (两个连通块)
    g = Graph(5, directed=False)
    g.add_edge(0, 1)
    g.add_edge(1, 2)
    g.add_edge(3, 4)

    assert g.connected_components() == 2
    assert g.degree(1) == 2
    assert g.has_path(0, 2) == True
    assert g.has_path(0, 4) == False

    # 有向图: 0->1->2->0 (环)
    dg = Graph(3, directed=True)
    dg.add_edge(0, 1)
    dg.add_edge(1, 2)
    dg.add_edge(2, 0)
    assert dg.degree(0) == 1   # 出度
    assert dg.in_degree(0) == 1
    assert dg.has_path(0, 2) == True

    print("All tests passed.")

易错点

• 无向图中(u,v)和(v,u)算一组重边，有向图中u->v和v->u不是重边
• 自环对度的贡献是2而非1(无向图)，计算度时需特殊处理
• 题目未说明时可能存在自环和重边，需特殊考虑
• 稀疏图用邻接表O(V+E)，稠密图可用邻接矩阵O(V²)避免常数

例题

信源

• OI Wiki✓ https://oi-wiki.org/graph/concept/
• 书籍✓ CPH ch11 pp119-126