图的存储：邻接表与链式前向星

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

        # 邻接表存图（Python）：日常首选。g[u] 是 u 的出边列表，加边就是 append，遍历就是 for，没有指针和链表。
# 顶点 0..n-1 用形态一（列表套列表）；顶点编号稀疏/不连续用形态二（defaultdict），遍历写法完全相同。
# 什么时候改用链式前向星（linklist.py）：需要给边一个稳定编号时，例如网络流的 i ^ 1 反向边、给边打标记。
# 无向边 = 两条有向边，各 append 一次；遍历顺序 = 加边顺序（链式前向星是头插法，顺序相反）。

from collections import defaultdict

# ===== 形态一：顶点 0..n-1（最常用）=====

n = 4                        # 顶点数，编号 0..n-1；按题面赋值
g = [[] for _ in range(n)]   # 列表套列表：每个 g[u] 是 u 的出边列表

# 加有向边 u -> v：带权存 (v, w)，无权直接存 v
g[0].append((1, 5))
g[0].append((2, 7))
g[1].append((3, 9))

# 加无向边 u - v：两个方向各存一次
g[0].append((1, 5))
g[1].append((0, 5))

# 遍历 u 的出边：顺序 = 加边顺序
for v, w in g[0]:
    pass

# 查询 u -> v 是否存在：扫 g[u]，O(出度)；要 O(1) 查边就换邻接矩阵
has_edge = any(v == 2 for v, _ in g[0])

# ===== 形态二：顶点编号稀疏/不连续 =====

h = defaultdict(list)   # 读不存在的点自动得到 []，不会 KeyError；空点不占额外判断
h[10].append((99, 1))   # 顶点编号可以是任意大整数，甚至字符串
for v, w in h[10]:
    pass

# 自检：加边顺序决定遍历顺序
assert [v for v, _ in g[0]] == [1, 2, 1]  # (1,5)、(2,7)、无向边 (1,5)
assert g[3] == []                          # 孤立点就是一个空列表
assert any(v == 2 for v, _ in g[0]) is has_edge
    

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

        # 链式前向星：head[u] 指向 u 最近加入的一条出边，边的 nxt 串起更早的边，None 表示链尾。
# 只在需要「边有稳定编号」时用它（网络流的 i ^ 1 反向边、给边打标记）；日常存图用邻接表 graph_adj.py。
# edges 是动态边表，等价于 C++ 的 e[maxe] + edge_cnt，边下标就是边编号；权值 w 是 Python int，不会溢出。

from collections.abc import Iterator
from dataclasses import dataclass


@dataclass(slots=True)
class Edge:
    """一条边：起点 u、终点 v、权值 w、同起点的下一条边下标 nxt（None 表示链尾）。"""

    u: int
    v: int
    w: int = 0
    nxt: int | None = None


class LinkList:
    """reset() 后所有点都没有出边；add/add_undirected 插到对应点链表头部。"""

    def __init__(self) -> None:
        self.reset()

    def reset(self) -> None:
        """清空整张图（对应 C++ 的 edge_cnt=0 + memset(head,-1)，多测记得调用）。"""
        self.edges: list[Edge] = []
        # 普通 dict：读用 get，不会像 defaultdict 那样一读就插入键，孤立点不占内存
        self.head: dict[int, int] = {}

    def add(self, u: int, v: int, w: int = 0) -> None:
        """加有向边 u->v，O(1) 插到 u 的链表头，返回前边数加一。"""
        self.edges.append(Edge(u, v, w, self.head.get(u)))
        self.head[u] = len(self.edges) - 1

    def add_undirected(self, u: int, v: int, w: int = 0) -> None:
        """加无向边 u<->v，等价于两条方向相反的有向边（对应 C++ 的 add2）。"""
        self.add(u, v, w)
        self.add(v, u, w)

    def out_edges(self, u: int) -> Iterator[Edge]:
        """for edge in g.out_edges(u) 遍历 u 的出边，最近加入的边优先（头插法）。"""
        i = self.head.get(u)
        while i is not None:
            edge = self.edges[i]
            yield edge
            i = edge.nxt

    def adj(self, u: int) -> Iterator[int]:
        """for v in g.adj(u) 只遍历 u 的出边终点。"""
        for edge in self.out_edges(u):
            yield edge.v


e = LinkList()
    

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

        # 链式前向星（raw 数组版）：head[u] 指向 u 最近加入的一条出边，0 表示没有出边。
# e 是边表，下标就是边编号；e[i] = (to, nxt, w) 对应 C++ 的 e[i].to / e[i].next / e[i].w。
# 0 号是哨兵，add_edge 加有向边、add_edge2 加无向边，边从 1 号开始编号。
# 遍历 u 的出边：i = head[u]，while i 时取 e[i] 的 to / w，再 i = nxt，走完 0 结束。

from collections import defaultdict

# (to, nxt, w)：终点、同起点的下一条边编号、权值
type Edge = tuple[int, int, int]

# 等价于 memset(head, 0)：读没出现过的点得到 0
head: defaultdict[int, int] = defaultdict(int)

# 0 号哨兵，让 head[u] == 0 能安全表示「无出边」
e: list[Edge] = [(0, 0, 0)]


def add_edge(u: int, v: int, weight: int = 1) -> None:
    """加有向边 u -> v：新边头插到 u 的链上，u == v 时也不会出错。"""
    e.append((v, head[u], weight))
    head[u] = len(e) - 1


def add_edge2(u: int, v: int, weight: int = 1) -> None:
    """加无向边 u - v：两个方向各插一条（对应 C++ 的 add2）。"""
    add_edge(u, v, weight)
    add_edge(v, u, weight)
    

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

        # 链式前向星（struct 精简版）：h[u] 指向 u 的第一条出边，next 串起后续边，-1 表示链尾。
# h 用 defaultdict(-1) 模拟 memset(h,-1) 的定长数组；e 是动态边表，替代 e[maxe]。
# 接口：add / add2 加边，out_edges(u) 遍历点 u 的出边，-1 表示链尾。
# e[i] = (u, v, w, nxt) 对应 C++ 的 e[i].u / e[i].v / e[i].w / e[i].next。

from collections import defaultdict
from collections.abc import Iterator

# (u, v, w, nxt)：起点、终点、权值、同起点的下一条边编号
type Edge = tuple[int, int, int, int]


class LinkList:
    """构造后图为空；add 把新边插到 u 的链表头，-1 表示链尾。"""

    def __init__(self) -> None:
        self.e: list[Edge] = []
        self.h: defaultdict[int, int] = defaultdict(lambda: -1)

    def add(self, u: int, v: int, w: int = 0) -> None:
        self.e.append((u, v, w, self.h[u]))
        self.h[u] = len(self.e) - 1

    def add2(self, u: int, v: int, w: int = 0) -> None:
        self.add(u, v, w)
        self.add(v, u, w)

    def out_edges(self, u: int) -> Iterator[Edge]:
        """遍历点 u 的出边：for u_, v, w, nxt in e.out_edges(u)，头插法，后加的边先出。"""
        i = self.h[u]
        while i != -1:
            edge = self.e[i]
            yield edge
            i = edge[3]  # nxt


e = LinkList()