算法设计与分析

运行一个完整示例 · 01

运行总数及其不变量

前缀是列表开头到某位置的部分。每来一个新值就打印总数。

values = [4, -1, 6, 2]
total = 0
prefixes = []
for value in values:
    total += value
    prefixes.append(total)
    print(value, total)
print(prefixes)

python analysis-correctness-prefix-total-trace.py

4 4
-1 3
6 9
2 11
[4, 3, 9, 11]

按执行顺序理解

1. 将 total 初始化为空前缀和 0，prefixes 为空列表。

2. 先加下个值再记录 total，保持已处理前缀不变量。

3. 打印每次变化，循环后打印完整前缀表。

逐步读懂代码

values 创建 Python 列表，total=0 设置初始和，空方括号建立空输出列表。for 按顺序让 value 取得每项，+= 加入旧总数，append 将新总数放末端。

第二列始终为已见值之和，这就是不变量。四项做四次加法，n 项时间 O(n)，保存所有前缀需 O(n) 额外空间。若只留最终和，在固定大小数值模型下只需 O(1) 额外变量。

运行一个完整示例 · 02

计算扩容存储的成本

把普通写入与容量翻倍引起的复制分开计数。

capacity = 1
size = 0
copies = 0
for value in [10, 20, 30, 40, 50]:
    if size == capacity:
        copies += size
        capacity *= 2
    size += 1
    print("size:", size, "capacity:", capacity, "copies:", copies)
print("writes plus copies:", size + copies)

python analysis-correctness-doubling-array-cost.py

size: 1 capacity: 1 copies: 0
size: 2 capacity: 2 copies: 1
size: 3 capacity: 4 copies: 3
size: 4 capacity: 4 copies: 3
size: 5 capacity: 8 copies: 7
writes plus copies: 12

按执行顺序理解

1. 从一个可用单元和零个值开始。

2. 每次写入前，仅在当前单元全满时翻倍。

3. 每次扩容对每个旧单元计一次复制，再计一次新写入。

逐步读懂代码

这是容量翻倍数组的成本模拟，不是 Python 列表分配器实现。size 统计已用单元。当 size 等于 capacity 时，全部旧引用都需要复制，因此先把 size 加入 copies，再把容量翻倍。

第五次追加引起四次复制，单独看很昂贵。五次追加合计七次复制和五次新写入。对于 n 次追加，等比复制总和小于 2n，因此在本模型下追加的摊还成本为 O(1)。这里没有随机选择。

运行一个完整示例 · 01

观察数组插入怎样移动值

手工建立插入过程，不藏在 list.insert 中。

items = ["L", "M", "N", "P"]
position = 1
items.append(None)
shifts = 0
for i in range(len(items) - 1, position, -1):
    items[i] = items[i - 1]
    shifts += 1
items[position] = "X"
print(items)
print("shifts:", shifts)

python lists-representations-array-insert-shifts.py

['L', 'X', 'M', 'N', 'P']
shifts: 3

按执行顺序理解

1. 追加备用单元，让末项有位置可去。

2. 从右往左复制，保留尚未复制的值。

3. 在位置 1 写 X，报告三次移动。

逐步读懂代码

append(None) 新建备用单元。None 是占位对象，不是文字 "None"。range(start,stop,-1) 逆序访问且不含 stop，倒着移动避免尚未复制的值被覆盖。

循环先移 P，再 N，再 M，最后将 X 写索引 1。输出三次引用移动。最坏需移 n 项，插入 O(n)。例子扩展 Python 列表，不展示物理地址。

运行一个完整示例 · 02

向真实链式节点中插入

程序已知节点 M，观察在 M 后插 X 而不移动 N。

class Node:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node

n = Node("N")
m = Node("M", n)
head = Node("L", m)
old_next = m.next
m.next = Node("X", old_next)
values = []
current = head
while current is not None:
    values.append(current.value)
    current = current.next
print(values)
print("X still links to N:", m.next.next is n)

python lists-representations-linked-node-splice.py

['L', 'M', 'X', 'N']
X still links to N: True

按执行顺序理解

1. 反向构建链，让每个 next 引用已存在。

2. 保存 M 后继，创建指向后继的 X，再让 M 指 X。

3. 沿 next 遍历，确认旧 N 对象仍连通。

逐步读懂代码

class 定义节点形状，Node(...) 创建时运行 __init__，self 指新节点。next 存引用，None 标末端。先建 N，才能让 M 指 N、L 指 M。

old_next 记住 N，新 X 指 N，M 改指 X。is 检查两引用是否到同一对象。编辑是常数工作。打印遍历用 O(n) 时间和 O(n) 结果表，展示成本与插入分开。

运行一个完整示例 · 01

用栈匹配括号

函数同时检查括号类型和顺序。

def balanced(text):
    stack = []
    opening = {')': '(', ']': '[', '}': '{'}
    for char in text:
        if char in "([{":
            stack.append(char)
        elif char in opening:
            if not stack or stack.pop() != opening[char]:
                return False
    return not stack

print(balanced("([])"))
print(balanced("([)]"))
print(balanced("(("))

python stacks-queues-stack-bracket-check.py

True
False
False

按执行顺序理解

1. 建立右到左的映射，初始无未匹配括号。

2. 左括号入栈；右括号必须安全弹出匹配栈顶。

3. 提前拒绝不匹配，扫描后拒绝剩余左括号。

逐步读懂代码

def 建可复用函数。opening 将每右括号映射到所需左括号。append 记录左括号，空栈时 not stack 为真，or 立即停止判断，因此不会不安全地 pop。

右括号只移除栈顶左括号，不匹配立即 False。结束时 not stack 拒绝剩余左括号，其他字符忽略。每字符检查一次，时间 O(n)，最多保存 n 个左括号，额外空间 O(n)。

运行一个完整示例 · 02

用 deque 服务等待任务

deque 是双端队列，右端到达，左端服务。

from collections import deque
queue = deque(["Ada", "Bo"])
queue.append("Cy")
print("served:", queue.popleft())
print("waiting:", list(queue))
queue.appendleft("urgent")
print("left end:", queue.popleft())
print("waiting:", list(queue))

python stacks-queues-deque-fifo-service.py

served: Ada
waiting: ['Bo', 'Cy']
left end: urgent
waiting: ['Bo', 'Cy']

按执行顺序理解

1. 把 Cy 追加在 Ada、Bo 后，保持到达顺序。

2. 从左移除 Ada，显示两个剩余任务。

3. 在左插 urgent，展示明确的策略改变。

逐步读懂代码

导入语句提供 deque。append 在右加入 Cy，popleft 移除最早的 Ada。list(queue) 仅为清晰打印而复制状态。

appendleft 展示另一操作，把 urgent 放在前面，改变服务策略，所以这一部分不再纯 FIFO。deque 两端增删 O(1)，复制全部项用于展示 O(n)。空 popleft 会抛 IndexError。

运行一个完整示例 · 01

比较三种遍历顺序

节点用标签、左分支、右分支组成元组，None 表示空分支。

tree = ("R", ("A", ("C", None, None), None), ("B", None, None))
def walk(node, order):
    if node is None:
        return []
    value, left, right = node
    first = walk(left, order)
    last = walk(right, order)
    if order == "pre":
        return [value] + first + last
    if order == "in":
        return first + [value] + last
    return first + last + [value]

for order in ["pre", "in", "post"]:
    print(order, walk(tree, order))

python trees-traversal-tree-three-orders.py

pre ['R', 'A', 'C', 'B']
in ['C', 'A', 'R', 'B']
post ['C', 'A', 'B', 'R']

按执行顺序理解

1. None 返回空序列，作为停止情形。

2. 递归取得左右顺序，再将当前标签放前、中或后。

3. 让同一棵树经过三种放置规则。

逐步读懂代码

元组组合三个值，value,left,right 赋值将其解包。None 情形返回空表并停止递归，两次调用处理更小分支，+ 按所需顺序拼接。

每输出都恰含每节点一次，但反复拼接复制结果。这个清楚版本在链上可能 O(n²) 时间，除 O(h) 调用栈外还有 O(n) 峰值临时列表存储。实际遍历可向一个结果表追加，得到 O(n) 时间、O(n) 输出和 O(h) 调用栈。

运行一个完整示例 · 02

同时计算大小与高度

每分支一次返回两项事实，避免再扫描。

tree = ("R", ("A", ("C", None, None), None), ("B", None, None))
def facts(node):
    if node is None:
        return 0, -1
    _, left, right = node
    left_size, left_height = facts(left)
    right_size, right_height = facts(right)
    return 1 + left_size + right_size, 1 + max(left_height, right_height)

size, height = facts(tree)
print("size:", size)
print("height:", height)
print("empty:", facts(None))

python trees-traversal-tree-size-height.py

size: 4
height: 2
empty: (0, -1)

按执行顺序理解

1. 空分支用 (0,-1)，让叶子也能套公式。

2. 向每个孩子同时请求大小和高度。

3. 父亲大小加一，高度取较长孩子加一。

逐步读懂代码

空分支返回大小 0、高度 −1。下划线说明标签未使用。递归返回一对，随后赋值解包；父亲相加大小、取较大高度。

根计四节点，最长 R–A–C 两边，高度 2。每节点只做一次常数合并，时间 O(n)。仅活动祖先调用占存储，额外 O(h)。小树远低于 Python 递归限制。

运行一个完整示例 · 01

插入键并记录搜索路线

这里使用真实链接树节点，不调用 Python 排序。

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
def insert(node, key):
    if node is None:
        return Node(key)
    if key < node.key:
        node.left = insert(node.left, key)
    elif key > node.key:
        node.right = insert(node.right, key)
    return node
root = None
for key in [18, 9, 27, 4, 13, 22, 31]:
    root = insert(root, key)
current = root
route = []
while current is not None:
    route.append(current.key)
    if current.key == 22:
        break
    current = current.left if 22 < current.key else current.right
print("route:", route)
print("found:", current is not None)

python bst-range-queries-bst-build-search.py

route: [18, 27, 22]
found: True

按执行顺序理解

1. 插入时重接递归返回的根。

2. 每次比较排除错误方向子树。

3. 到 22 或 None 停止，并记录路线供检查。

逐步读懂代码

Node 初始有两个空孩子。insert 返回更新分支的根，赋给 node.left 或 node.right 才保持新孩子连接。相等键不进任何分支，因此只保存唯一键。

while 记录每次比较，条件表达式在目标较小时选左，否则选右，三次访问到 22。搜索 O(h) 时间、O(1) 工作引用，route 另用 O(h) 展示空间。递归插入用 O(h) 栈，不会平衡。

运行一个完整示例 · 02

报告区间并剪掉无用分支

用嵌套元组保持示例简短，每元组依次为键、左、右。

tree = (18, (9, (4, None, None), (13, None, None)),
            (27, (22, None, None), (31, None, None)))
def report(node, low, high, result):
    if node is None:
        return
    key, left, right = node
    if low < key:
        report(left, low, high, result)
    if low <= key <= high:
        result.append(key)
    if key < high:
        report(right, low, high, result)
result = []
report(tree, 10, 28, result)
print(result)

python bst-range-queries-bst-pruned-range.py

[13, 18, 22, 27]

按执行顺序理解

1. 检查左子树是否可能与下界相交。

2. 仅当当前键满足包含两端的界时追加。

3. 独立检查右子树，以保持中序输出。

逐步读懂代码

各调用共享一个 result。只有更小键仍可能达到 low 才进入左子树；当前键同时满足上下界才追加；更大键仍可能低于 high 才进入右子树。

三动作按中序进行，因此输出有序。测试跳过以 4 为根的分支；仍会访问 31，但不输出它，也不进入其右子树。唯一键、有效 BST 下时间 O(h+k)，输出 O(k)，递归调用 O(h)。假设 low 不大于 high。

运行一个完整示例 · 01

向右旋转外侧偏重分支

所有节点保存高度，辅助函数在链接改变后重算高度。

class Node:
    def __init__(self, key):
        self.key, self.left, self.right, self.height = key, None, None, 0
def height(node):
    return -1 if node is None else node.height
def update(node):
    node.height = 1 + max(height(node.left), height(node.right))
def rotate_right(root):
    new_root = root.left
    root.left = new_root.right
    new_root.right = root
    update(root)
    update(new_root)
    return new_root
root = Node(30)
root.left = Node(20)
root.left.left = Node(10)
update(root.left)
update(root)
print("before height:", root.height)
root = rotate_right(root)
print("keys:", root.left.key, root.key, root.right.key)
print("after height:", root.height)

python avl-balance-avl-single-rotation.py

before height: 2
keys: 10 20 30
after height: 1

按执行顺序理解

1. 建立 30→20→10，从叶向上更新高度。

2. 提升左孩子，同时把中间子树转给旧根。

3. 先更新旧根，再更新新根，检查高度与顺序。

逐步读懂代码

类保存键、两个链接和高度，height(None) 给空分支约定，update 使用已存孩子高度。rotate_right 先保存左孩子，将其旧右分支移到旧根左边，再让旧根成为它右孩子。

先更新旧根使新根高度计算有效。打印键保持同一排序，高度从 2 降为 1。有已存高度时每次旋转 O(1) 时间和空间，寻找修复点仍 O(h)。函数假设左孩子存在。

运行一个完整示例 · 02

修复内侧偏重分支

先左旋理顺 30–10–20，再右旋。

class Node:
    def __init__(self, key, left=None, right=None):
        self.key, self.left, self.right = key, left, right
def rotate_left(root):
    top = root.right
    root.right = top.left
    top.left = root
    return top
def rotate_right(root):
    top = root.left
    root.left = top.right
    top.right = root
    return top
root = Node(30, Node(10, right=Node(20)))
root.left = rotate_left(root.left)
print("after first:", root.key, root.left.key, root.left.left.key)
root = rotate_right(root)
print("after second:", root.left.key, root.key, root.right.key)

python avl-balance-avl-double-rotation.py

after first: 30 20 10
after second: 10 20 30

按执行顺序理解

1. 先识别左—右弯，再选择修复。

2. 在孩子 10 左旋，把返回的 20 重新接到 30。

3. 在 30 右旋，让 20 成根，检查两孩子。

逐步读懂代码

初始树先左后右弯，rotate_left 把 20 提到 10 上，变成左链。root.left 赋值把变化分支接回，rotate_right 再把 20 提到 30 上。

最终按左、根、右打印 10、20、30，链接修改 O(1)。为集中说明形状，此第二例省略高度字段；完整 AVL 必须像首例那样在两次旋转后更新元数据。两函数都不处理所需孩子缺失的情况。

运行一个完整示例 · 01

用 heapq 按优先级服务

heapify 建堆，heappop 移除最小项。

import heapq
jobs = [8, 3, 5, 12, 10]
heapq.heapify(jobs)
print("minimum:", jobs[0])
heapq.heappush(jobs, 4)
served = []
while jobs:
    served.append(heapq.heappop(jobs))
print("served:", served)

python priority-queues-heaps-heapq-priority-service.py

minimum: 3
served: [3, 4, 5, 8, 10, 12]

按执行顺序理解

1. 将五任务建堆，读取根为最小值。

2. 压入优先级 4，由 heapq 恢复父子顺序。

3. 反复移除最小值，扩展有序服务历史。

逐步读懂代码

import 导入标准库。heapify 原地重排列表成堆，不返回新排序表。jobs[0] 读最小，heappush 加 4 并修复。

while jobs 重复到空，每次 heappop 返回当前最小，因此 served 有序而内部堆未全排。建堆 O(n)，每次 push/pop O(log n)，全取 O(n log n)。输出表额外 O(n)。

运行一个完整示例 · 02

亲自编写堆插入修复

观察新值 4 从索引 5 移到 2。

heap = [3, 8, 5, 12, 10]
heap.append(4)
i = len(heap) - 1
swaps = 0
while i > 0:
    parent = (i - 1) // 2
    if heap[parent] <= heap[i]:
        break
    heap[parent], heap[i] = heap[i], heap[parent]
    i = parent
    swaps += 1
print(heap)
print("swaps:", swaps)
print("valid:", all(heap[(j - 1) // 2] <= heap[j] for j in range(1, len(heap))))

python priority-queues-heaps-heap-bubble-up.py

[3, 8, 4, 12, 10, 5]
swaps: 1
valid: True

按执行顺序理解

1. 追加 4，令 i 为新索引 5。

2. 与父索引 2 比较并交换违法的一对。

3. 在 3 下停止，再独立检查全部父不等式。

逐步读懂代码

新值从最后索引开始，// 找父。if 在父已不大于孩子时停止，成对赋值交换而不丢任一值，i=parent 从新位置继续向上。

只有 4、5 交换。all 检查全部非根父不等式，此最终检查 O(n)，不是 O(log n) 插入修复的一部分。修复额外 O(1) 变量，假设原数组已满足堆序。

运行一个完整示例 · 01

观察插入排序扩展前缀

每次插入后打印数组，并计移动数量。

values = [5, 2, 4, 1]
shifts = 0
for i in range(1, len(values)):
    item = values[i]
    j = i - 1
    while j >= 0 and values[j] > item:
        values[j + 1] = values[j]
        j -= 1
        shifts += 1
    values[j + 1] = item
    print(values)
print("shifts:", shifts)

python sorting-baselines-insertion-sort-trace.py

[2, 5, 4, 1]
[2, 4, 5, 1]
[1, 2, 4, 5]
shifts: 5

按执行顺序理解

1. 移动前保存下个未排项。

2. 把前缀更大值右移，直到找到插入空位。

3. 写入保存项，打印扩大的有序前缀。

逐步读懂代码

range 从 1 开始，因为单项前缀已有序。item 保存下一值以免被移动覆盖。j 向左走，and 先查边界再读数组，每个较大值右移一格。

循环后 j+1 为正确空位，到 i 的前缀已有序，后面还在等待。输出展示此不变量增长。最坏 O(n²)，有序输入 O(n)，额外少量变量 O(1)。

运行一个完整示例 · 02

反复移除堆最小值完成排序

这是使用独立结果表的清晰堆排序版本。

import heapq
values = [5, 2, 4, 1]
heap = values.copy()
heapq.heapify(heap)
result = []
while heap:
    result.append(heapq.heappop(heap))
print("input:", values)
print("sorted:", result)

python sorting-baselines-heap-sort-output.py

input: [5, 2, 4, 1]
sorted: [1, 2, 4, 5]

按执行顺序理解

1. 复制输入，保留原表供比较。

2. 在副本上建小顶堆。

3. 把每次移除的最小值追加到 result，直到堆空。

逐步读懂代码

copy 保留原表，heapify 用 O(n) 时间将副本建为小顶堆。heappop 返回剩余最小，因此 append 扩展已排序结果。

共有 n 次移除，每次至多 O(log n)，总 O(n log n)。堆副本与结果共额外 O(n)。展示堆排序机制，不是常数空间大顶堆版。程序排序数字，相等键记录需另定稳定策略。

运行一个完整示例 · 01

把碰撞键放进同一桶

用整数余数构建小映射，使桶位置输出确定。

buckets = [[] for _ in range(7)]
for key, value in [(10, "ten"), (17, "seventeen"), (24, "twenty-four")]:
    buckets[key % 7].append((key, value))
print("bucket 3:", buckets[3])
def lookup(key):
    for stored_key, value in buckets[key % 7]:
        if stored_key == key:
            return value
    return None
print("24:", lookup(24))
print("31:", lookup(31))

python hashing-collisions-hash-chaining-buckets.py

bucket 3: [(10, 'ten'), (17, 'seventeen'), (24, 'twenty-four')]
24: twenty-four
31: None

按执行顺序理解

1. 建立七个独立桶表，而不是同表的七个引用。

2. 把整数键送到 key%7，并保留配对值。

3. 对存在的 24 和缺失的 31 都扫描桶 3，并检查真实键相等。

逐步读懂代码

列表推导式创建七个独立空表，下划线表示循环编号未用。key%7 选桶，append 存键值元组。lookup 只扫该桶并比真实键。

31 也进此桶但不存在，函数返回 None。此只插演示假设输入键各不相同；完整映射重复键应替旧值。查找随桶长变化，最坏 O(n)，仅哈希合适时才期望 O(1+α)。

运行一个完整示例 · 02

删除时保留探测链

用唯一对象标记删除槽，不打印对象，因此输出不依赖地址。

deleted = object()
table = [None] * 7
for key in [10, 17, 24]:
    index = key % 7
    while table[index] is not None:
        index = (index + 1) % 7
    table[index] = key
table[4] = deleted
def contains(key):
    visited = []
    for offset in range(len(table)):
        index = (key % 7 + offset) % 7
        visited.append(index)
        item = table[index]
        if item is None:
            return False, visited
        if item is not deleted and item == key:
            return True, visited
    return False, visited
print(contains(24))
table[4] = None
print(contains(24))

python hashing-collisions-linear-probe-tombstone.py

(True, [3, 4, 5])
(False, [3, 4])

按执行顺序理解

1. 把三碰撞键放入相邻槽。

2. 用标记删 17，验证查 24 能越过它。

3. 把标记换 None，展示错误的停止规则。

逐步读懂代码

object() 建唯一标记。初始插入把 10、17、24 放槽 3、4、5。槽 4 换 deleted 模拟删 17。contains 至多检查表长，防止无限搜索。

is not 通过身份识别标记。首次搜索越过 4 并找到 24，换 None 后第二次过早结束。探测可 O(m)。初始插入循环仅用于已知非满输入，完整实现还需满表检测和墓碑复用。

运行一个完整示例 · 01

追踪有界的布谷鸟插入

固定两哈希规则用于小演示，说明迁移而非通用好哈希。

first = [None] * 3
second = [None] * 3
def insert(key):
    board = 0
    for _ in range(8):
        table = first if board == 0 else second
        index = key % 3 if board == 0 else (key // 3) % 3
        table[index], key = key, table[index]
        if key is None:
            return
        board = 1 - board
    raise RuntimeError("Rebuild required; an evicted key remains")
for key in [0, 3, 6]:
    insert(key)
print("first:", first)
print("second:", second)
print("3 found:", first[3 % 3] == 3 or second[(3 // 3) % 3] == 3)

python cuckoo-maps-sets-cuckoo-two-home-demo.py

first: [6, None, None]
second: [0, 3, None]
3 found: True

按执行顺序理解

1. 先尝试新键在第一表的位置。

2. 在局部变量保留被逐键，移到另一表。

3. 只在空槽结束；达到移动上限则报告需重建。

逐步读懂代码

board 选表，成对赋值安装新键并用 key 保留被逐出键。若被逐值为 None 就找到空位，否则 1−board 切换其另一板。

最终 0、3、6 都有合法位置，查找只看两单元。插入可能多步。异常只报告失败，不实现重建或回滚；失败时有待放键在表外。仅所演示成功输入构成完整插入序列。

运行一个完整示例 · 02

区分成员与次数

用标准库容器展示不同集合契约。

from collections import Counter
colors = ["red", "blue", "red"]
members = set(colors)
counts = Counter(colors)
print("red present:", "red" in members)
print("distinct:", len(members))
print("red count:", counts["red"])
print("total:", sum(counts.values()))

python cuckoo-maps-sets-set-and-counter-contracts.py

red present: True
distinct: 2
red count: 2
total: 3

按执行顺序理解

1. 两个容器都使用相同三次颜色出现。

2. 向 set 查成员，向 Counter 查 red 次数。

3. 比较不同成员数与出现总次数。

逐步读懂代码

set 去重成员，Counter 构建每色到次数的映射。in 问成员，方括号取计数，values 取各计数，sum 相加。

输出区分两种颜色与三次出现。不打印集合，因为迭代顺序不适合作稳定输出。代码讲集合语义，不是布谷鸟内部。通常哈希假设下计数 n 项期望 O(n)，k 种颜色空间 O(k)。

运行一个完整示例 · 01

建立无向邻接表

用普通字典把每个房间映射到邻居列表。

vertices = ["A", "B", "C", "D", "E"]
edges = [("A", "B"), ("A", "C"), ("B", "D"), ("C", "D")]
graph = {vertex: [] for vertex in vertices}
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)
for vertex in vertices:
    print(vertex, graph[vertex])
print("degree sum:", sum(len(graph[v]) for v in vertices))
print("twice edges:", 2 * len(edges))

python graph-models-adjacency-list-degree-check.py

A ['B', 'C']
B ['A', 'D']
C ['A', 'D']
D ['B', 'C']
E []
degree sum: 8
twice edges: 8

按执行顺序理解

1. 为每顶点建字典项，包括孤立 E。

2. 在两端都记录每条无向边。

3. 统计全部邻居项，与边数两倍比较。

逐步读懂代码

字典推导式给每房独立列表，包括孤立 E。循环把边解包为 u、v，再记录双向，按原顶点表迭代保证输出顺序确定。

此简单图中 len(graph[v]) 为度，sum 加五个度。建立列表 O(n+m) 时间与空间。Python 列表查某邻居可 O(degree)，邻接表存储不自动提供常数成员查询。

运行一个完整示例 · 02

用矩阵空间换取直接查边

存储有向图。方向使对称的两个矩阵单元可以不同。

vertices = ["A", "B", "C"]
index = {v: i for i, v in enumerate(vertices)}
matrix = [[False] * 3 for _ in vertices]
for u, v in [("A", "B"), ("B", "C")]:
    matrix[index[u]][index[v]] = True
print("A to B:", matrix[index["A"]][index["B"]])
print("B to A:", matrix[index["B"]][index["A"]])
neighbors = [vertices[j] for j in range(3) if matrix[index["B"]][j]]
print("B neighbors:", neighbors)
print("cells:", sum(len(row) for row in matrix))

python graph-models-matrix-edge-tests.py

A to B: True
B to A: False
B neighbors: ['C']
cells: 9

按执行顺序理解

1. 建立标签到索引的字典和三个独立行。

2. 设置 A→B 与 B→C，不设置反向单元。

3. 查边时读取一个单元，找邻居时扫描整行。

逐步读懂代码

enumerate 提供索引和标签，字典把标签映射到索引。每次推导式迭代建立独立行；如果重复使用同一行，更新会错误影响其他行。这里仅设置有向边对应的单元。

确定索引后，查边使用 O(1) 数组操作。列出 B 的邻居要扫描全部 n 列，即使只有一条边。建立 n 行 n 列矩阵需要 O(n²) 时间和空间。稠密图或频繁查边可能适合它；稀疏图遍历通常适合邻接表。

运行一个完整示例 · 01

用发现时间与 low 找桥

这是没有平行边或自环的简单无向小图。

graph = {"A": ["B", "C"], "B": ["A", "C"],
         "C": ["B", "A", "D"], "D": ["C"]}
discovery = {}
low = {}
bridges = []
def dfs(u, parent=None):
    discovery[u] = len(discovery)
    low[u] = discovery[u]
    for v in graph[u]:
        if v == parent:
            continue
        if v not in discovery:
            dfs(v, u)
            low[u] = min(low[u], low[v])
            if low[v] > discovery[u]:
                bridges.append((u, v))
        else:
            low[u] = min(low[u], discovery[v])
for vertex in graph:
    if vertex not in discovery:
        dfs(vertex)
print("discovery:", discovery)
print("low:", low)
print("bridges:", bridges)

python dfs-bridges-dfs-low-bridge-trace.py

discovery: {'A': 0, 'B': 1, 'C': 2, 'D': 3}
low: {'A': 0, 'B': 0, 'C': 0, 'D': 3}
bridges: [('C', 'D')]

按执行顺序理解

1. 首次进入时分配发现编号并初始化 low。

2. 完成每个未见孩子，再传播 low 并检查桥条件。

3. 用非父已访问边降低 low，并在未见分量重启 DFS。

逐步读懂代码

discovery 字典同时充当已访问标记，其长度提供下个编号。continue 跳过进入边。未见邻居引起递归，只有返回后才使用最终 low。

else 处理已访问邻居，严格比较仅把 C–D 加入 bridges。外循环也覆盖不连通分量，每邻接项检查一次，时间 O(n+m)。字典、桥输出与递归调用连同输入总体 O(n+m)，排除输入的辅助状态 O(n)，递归可深 O(n)。深图可能超过 Python 递归限制。

运行一个完整示例 · 02

不用递归调用完成探索

栈保存尚待访问的顶点。此例求可达性，不计算桥所需的 low 值。

graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": [], "X": []}
stack = ["A"]
seen = set()
order = []
while stack:
    u = stack.pop()
    if u in seen:
        continue
    seen.add(u)
    order.append(u)
    for v in reversed(graph[u]):
        if v not in seen:
            stack.append(v)
print("order:", order)
print("X reachable:", "X" in seen)

python dfs-bridges-dfs-explicit-stack.py

order: ['A', 'B', 'D', 'C']
X reachable: False

按执行顺序理解

1. 栈最初只有 A，seen 集合为空。

2. 取出顶点，跳过已处理项，记录首次访问。

3. 逆序压入邻居，让下一次出栈沿预期分支深入。

逐步读懂代码

pop 取出最近入栈的顶点。reversed 逆序压入所列邻居，使 B 在 C 之前被探索。出栈时才标记，允许待处理项重复；seen 检查跳过重复项。这种策略保持熟悉的深度优先访问顺序。

每个到达顶点只展开一次邻接表，时间为 O(n+m)。允许重复项的待处理栈最多使用 O(n+m) 空间。显式栈避免 Python 递归深度限制。若要计算 low 值，栈帧还需记录下一个邻居以及子调用返回步骤；这个简单栈本身不实现桥检测。

运行一个完整示例 · 01

用队列求距离与路线

孤立顶点 X 展示不可达目的地的表示。

from collections import deque
graph = {"S": ["A", "B"], "A": ["S", "C"], "B": ["S", "D"],
         "C": ["A", "E"], "D": ["B", "E"], "E": ["C", "D"], "X": []}
distance = {vertex: None for vertex in graph}
parent = {"S": None}
distance["S"] = 0
queue = deque(["S"])
while queue:
    u = queue.popleft()
    for v in graph[u]:
        if distance[v] is None:
            distance[v] = distance[u] + 1
            parent[v] = u
            queue.append(v)
route = []
current = "E"
while current is not None:
    route.append(current)
    current = parent[current]
route.reverse()
print("distance to E:", distance["E"])
print("route:", route)
print("distance to X:", distance["X"])

python bfs-distance-bfs-distance-and-route.py

distance to E: 3
route: ['S', 'A', 'C', 'E']
distance to X: None

按执行顺序理解

1. S 初始化零，其他距离 None。

2. 先给未见邻居距离和父亲，再入队。

3. 逆向走 E 父链再反转，保留 X 缺失标记。

逐步读懂代码

距离字典用 None 标未见顶点，popleft 保持到达顺序。if 块在追加前设置距离与父亲，因此不会入队两次。

第二循环从 E 沿父亲回 S，reverse 将逆向表变正向。本例 E 已到达所以安全，一般查询需先检查。X 保留 None，代表本程序无穷。时间 O(n+m)，工作与父信息额外 O(n)，路线输出至多 O(n)。

运行一个完整示例 · 02

求到最近起点的距离

从路径两端同时开始。所有起点的距离都是零。

from collections import deque
graph = {0: [1], 1: [0, 2], 2: [1, 3], 3: [2, 4], 4: [3]}
sources = [0, 4]
distance = {v: None for v in graph}
queue = deque()
for source in sources:
    distance[source] = 0
    queue.append(source)
while queue:
    u = queue.popleft()
    for v in graph[u]:
        if distance[v] is None:
            distance[v] = distance[u] + 1
            queue.append(v)
print("nearest distances:", [distance[v] for v in range(5)])

python bfs-distance-multi-source-bfs.py

nearest distances: [0, 1, 2, 1, 0]

按执行顺序理解

1. 给起点 0、4 赋距离零，并全部入队。

2. 两端的首次扩展发现顶点 1、3，距离为 1。

3. 以距离 2 发现中点一次，忽略后来到达的重复路线。

逐步读懂代码

探索前把两个起点放进同一个先进先出队列。首次发现仍按距离层递增。各起点的路线在同一顺序中竞争，因此顶点得到的是到任一起点的最少边数。

顶点 2 到两端都需两条边，但只标记一次。这是一次 O(n+m) 遍历，不是对每个起点分别运行 BFS。距离表与队列使用 O(n) 空间。本例起点有效且互不相同。结果不统计有多少个最近起点并列。

运行一个完整示例 · 03

让 BFS 同时从所有出口出发

学校地图有两个出口。米娜想知道每个位置到最近出口需要走几步。如果从每个格子分别搜索，会重复大量工作。她把两个出口都以距离零加入同一个队列，让两股波同时扩散。某个格子第一次被波到达时，就得到了到最近出口的距离。

from collections import deque

def nearest_exit(grid, exits):
    rows, cols = len(grid), len(grid[0])
    if any(len(row) != cols for row in grid):
        raise ValueError("rectangular grid required")
    distance = {}
    queue = deque()
    for r, c in exits:
        if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] == "#":
            raise ValueError("exit must be an open cell")
        if (r, c) not in distance:
            distance[r, c] = 0
            queue.append((r, c))
    while queue:
        r, c = queue.popleft()
        for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nr, nc = r + dr, c + dc
            if (0 <= nr < rows and 0 <= nc < cols and
                    grid[nr][nc] != "#" and (nr, nc) not in distance):
                distance[nr, nc] = distance[r, c] + 1
                queue.append((nr, nc))
    return distance

grid = ["..#.", "....", ".#.."]
distance = nearest_exit(grid, [(0, 0), (2, 3)])
assert distance[0, 3] == 2 and distance[1, 1] == 2
assert nearest_exit(grid, []) == {}
for r, row in enumerate(grid):
    print(" ".join("#" if cell == "#" else str(distance.get((r, c), "X"))
                   for c, cell in enumerate(row)))

python bfs-distance-nearest-exit-wavefront.py

0 1 # 2
1 2 2 1
2 # 1 0

按执行顺序理解

1. 处理格子之前先放入全部出口，每个出口都在距离零这一层。

2. 入队时立即标记，避免两股波反复加入同一格子。

3. 每次合法移动增加一步，FIFO 顺序保证先处理完较近层。

4. 墙显示 #，不可达空格显示 X；缺失结果不能默认为距离零。

逐步读懂代码

目标是 d(v)=对所有出口 s 取 min dist(s,v)。不变量是：出队格子拥有尚未处理格子中最小的“到源点集合距离”。如果新格子还有更短路线，那条路线的前驱应当更早被处理。

R 行 C 列的网格最多有 RC 个格子，每格最多四条边，时间和空间都是 O(RC)。本例假设非空矩形网格、双向移动、每步成本相同。若走廊单向，要在反向图上从出口搜索，才能求各点到出口的距离。若成本不相等但非负，应改用多源 Dijkstra。

小网格只是算法示例，不是疏散规划器；它没有考虑拥堵、门的状态及随时间变化的条件。真正值得迁移的工程思路是：先明确所求方向与成本，再选择图算法。

运行一个完整示例 · 01

用惰性堆追踪更短路线

独立示例使用非负整数权有向图。

import heapq
graph = {"S": [("A", 6), ("B", 2)], "B": [("A", 1), ("C", 7)],
         "A": [("C", 3)], "C": []}
distance = {v: float("inf") for v in graph}
distance["S"] = 0
parent = {}
heap = [(0, "S")]
while heap:
    cost, u = heapq.heappop(heap)
    if cost != distance[u]:
        continue
    for v, weight in graph[u]:
        candidate = cost + weight
        if candidate < distance[v]:
            distance[v] = candidate
            parent[v] = u
            heapq.heappush(heap, (candidate, v))
route = ["C"]
while route[-1] != "S":
    route.append(parent[route[-1]])
route.reverse()
print("distances:", [(v, distance[v]) for v in ["S", "A", "B", "C"]])
print("route:", route)

python dijkstra-relaxation-dijkstra-lazy-heap.py

distances: [('S', 0), ('A', 3), ('B', 2), ('C', 6)]
route: ['S', 'B', 'A', 'C']

按执行顺序理解

1. 压入源点零距离候选，其他标签无穷。

2. 跳过旧候选，否则用完整路线成本松弛出边。

3. 每次改善同时更新父亲，并重建可达目的地路线。

逐步读懂代码

邻居项为目的点与权重对。float("inf") 大于任意有限成本。堆先按成本、并列时按字符串标签排序，失效检查跳过旧候选。

成功松弛更新距离及父亲，再加入新候选。路线逆走父链后反转，假设 C 可达。全部顶点都在字典键中。惰性法可排 O(m) 项，额外空间 O(n+m)，一般时间 O(n+(m+1)log(m+2))。这些小示例不测试负权输入。

运行一个完整示例 · 02

不用堆选择最小距离

逐项扫描使定点过程清楚可见，并明确保留不可达顶点。

graph = {"S": [("A", 0), ("B", 5)], "A": [("B", 2)], "B": [], "X": []}
distance = {v: float("inf") for v in graph}
distance["S"] = 0
settled = set()
while True:
    candidates = [v for v in graph if v not in settled]
    if not candidates:
        break
    u = min(candidates, key=lambda v: distance[v])
    if distance[u] == float("inf"):
        break
    settled.add(u)
    print("settled:", u, distance[u])
    for v, weight in graph[u]:
        distance[v] = min(distance[v], distance[u] + weight)
print("X:", distance["X"])

python dijkstra-relaxation-dijkstra-array-choice.py

settled: S 0
settled: A 0
settled: B 2
X: inf

按执行顺序理解

1. 仅把 S 初始化为零，其他距离均为无穷大。

2. 扫描未定点距离，把最小有限值定点。

3. 松弛出边；仅剩不可达顶点时停止。

逐步读懂代码

候选列表包含全部未定点顶点。min 扫描距离；key=lambda v: distance[v] 告诉 Python 比较哪个量。零权边有效，所以 A 可以在与 S 相同的距离定点。

当剩余顶点都不可达时，无穷大检查结束循环。最多 n 次扫描，每次最多 n 个顶点，成本 O(n²)；边松弛另加 O(m)。图之外的工作存储为 O(n)。对于稠密图，这是合理的简单替代方法。它仍要求非负权重；改变容器不会消除 Dijkstra 的假设。

运行一个完整示例 · 03

用 Bellman–Ford 处理负权边

米娜为路线打分，某个训练站的奖励可以表示为负权边。她不能再认为当前分数较小的节点已经永久确定。于是改问一个更稳妥的问题：最多用一条边、两条边、三条边时，最佳分数分别是多少？若可达环让分数一直下降，她就报告不存在有限最优值，而不是输出误导性的路线。

from math import inf

def bellman_ford(nodes, edges, source):
    distance = {node: inf for node in nodes}
    distance[source] = 0
    history = [distance.copy()]
    for _ in range(len(nodes) - 1):
        next_distance = distance.copy()
        for u, v, cost in edges:
            if distance[u] != inf:
                next_distance[v] = min(next_distance[v], distance[u] + cost)
        history.append(next_distance.copy())
        if next_distance == distance:
            break
        distance = next_distance
    if any(distance[u] != inf and distance[u] + w < distance[v]
           for u, v, w in edges):
        raise ValueError("reachable negative cycle")
    return distance, history

nodes = ["S", "A", "B", "C", "Z"]
edges = [("S", "A", 4), ("S", "B", 5), ("A", "B", -2),
         ("B", "C", 3), ("Z", "Z", -1)]
distance, history = bellman_ford(nodes, edges, "S")
assert distance == {"S": 0, "A": 4, "B": 2, "C": 5, "Z": inf}
for k, row in enumerate(history[:4]):
    print(f"at most {k} edges:", [row[v] for v in nodes[:4]])
print("Z is unreachable:", distance["Z"] == inf)
try:
    bellman_ford(nodes, edges + [("C", "A", -6)], "S")
except ValueError as error:
    print(error)

python dijkstra-relaxation-negative-edge-relaxation.py

at most 0 edges: [0, inf, inf, inf]
at most 1 edges: [0, 4, 5, inf]
at most 2 edges: [0, 4, 2, 8]
at most 3 edges: [0, 4, 2, 5]
Z is unreachable: True
reachable negative cycle

按执行顺序理解

1. 源点距离设为零，其他设为无穷。零条边只能到达源点。

2. 读取旧字典、写入新字典，每轮最多多用一条边，严格对应不变量。

3. 最多运行 |V|-1 轮。没有可达负环时，可以选择不重复顶点的最短路径。

4. 再尝试一轮松弛，若还能改善就存在可达负环；忽略 Z 这类不可达起点。

逐步读懂代码

递推式为 d_k(v)=min(d_(k-1)(v), 对所有 u→v 取 min[d_(k-1)(u)+w(u,v)])。下标 k 限制边数，不是时间距离。无穷表示暂时没有找到路线，不是随便选的很大整数。

|V| 个顶点、|E| 条边的最坏时间为 O(|V||E|)。工作距离数组只需要 O(|V|) 空间，但教学版还保存历史，空间可达 O(|V|²)。Z 上的负自环不影响从 S 出发的路线，因为 Z 不可达。如果存在可达负环，本实现拒绝整个查询，而不是分别标记哪些终点受影响。

逐轮复制的版本比原地更新更容易跟踪。原地更新在一轮内可能传播多条边。两种写法都可能正确，但中间表的含义不同，不要拿一种实现的不变量解释另一种。

运行一个完整示例 · 01

用并查集执行 Kruskal

并查集父链接追踪连通分组，不是真实电缆路线。

vertices = ["A", "B", "C", "D"]
edges = [(1, "A", "B"), (2, "B", "C"), (4, "A", "C"),
         (3, "C", "D"), (6, "B", "D")]
parent = {v: v for v in vertices}
size = {v: 1 for v in vertices}
def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x
chosen = []
total = 0
for weight, u, v in sorted(edges):
    a, b = find(u), find(v)
    if a == b:
        continue
    if size[a] < size[b]:
        a, b = b, a
    parent[b] = a
    size[a] += size[b]
    chosen.append((u, v, weight))
    total += weight
print("edges:", chosen)
print("total:", total)

python minimum-spanning-trees-kruskal-union-find.py

edges: [('A', 'B', 1), ('B', 'C', 2), ('C', 'D', 3)]
total: 6

按执行顺序理解

1. 排序边前为每顶点建立父与大小记录。

2. 查端点代表，跳过分量内部边。

3. 把小组合并到大组，另行记录接受的真实图边。

逐步读懂代码

每顶点起初自己作代表。find 沿父链接到根，赋值到祖父缩短未来路径，称路径减半压缩。sorted 首先按边元组的权排序。

代表相同表示加边成环，否则小组合并到大组并累加大小。所选边 1+2+3=6。排序 O(m log m)，分组操作近线性摊还。本版单独排序表和输出额外 O(n+m)。不连通输入产生森林，不是单棵生成树。

运行一个完整示例 · 02

跨割扩展最小生成树

Prim 选择最便宜的跨割边，不加上从源点出发的距离。

import heapq
graph = {"A": [("B", 1), ("C", 4)], "B": [("A", 1), ("C", 2), ("D", 6)],
         "C": [("A", 4), ("B", 2), ("D", 3)], "D": [("B", 6), ("C", 3)]}
visited = {"A"}
heap = [(w, "A", v) for v, w in graph["A"]]
heapq.heapify(heap)
chosen = []
total = 0
while heap:
    weight, u, v = heapq.heappop(heap)
    if v in visited:
        continue
    visited.add(v)
    chosen.append((u, v, weight))
    total += weight
    for neighbor, cost in graph[v]:
        if neighbor not in visited:
            heapq.heappush(heap, (cost, v, neighbor))
print("edges:", chosen)
print("total:", total)
print("spans graph:", len(visited) == len(graph))

python minimum-spanning-trees-prim-cut-frontier.py

edges: [('A', 'B', 1), ('B', 'C', 2), ('C', 'D', 3)]
total: 6
spans graph: True

按执行顺序理解

1. 从 A 开始，把离开 A 的边放进小顶堆。

2. 仅在最便宜边到达新顶点时接受它。

3. 加入新的边界边，跳过旧项，累计所选边权。

逐步读懂代码

visited 定义割的一侧。每个新堆项连接一个已访问顶点和当时尚未访问的顶点。目的顶点加入树后，旧项可能失效；成员检查会丢弃它。根据割论证，剩余最小跨割边可以安全选择。

接受的成本是 1、2、3。与 Dijkstra 不同，优先级只是跨割边权。这个保留旧边项的实现需要 O(n+m log(m+1)) 时间，包含图在内的空间为 O(n+m)。若输入不连通，从一个起点只能覆盖其所在分量；最后的布尔值明确显示这一限制。

运行一个完整示例 · 01

追踪可分背包

价值表示抽象实用积分，输入重量正且内容可拆分。

items = [("A", 4, 28), ("B", 5, 25), ("C", 6, 18)]
remaining = 10
total = 0.0
for name, weight, value in sorted(items, key=lambda item: item[2] / item[1], reverse=True):
    taken_weight = min(weight, remaining)
    fraction = taken_weight / weight
    total += fraction * value
    remaining -= taken_weight
    print(name, "weight:", taken_weight, "fraction:", round(fraction, 3))
    if remaining == 0:
        break
print("total value:", total)

python greedy-fractional-fractional-knapsack-trace.py

A weight: 4 fraction: 1.0
B weight: 5 fraction: 1.0
C weight: 1 fraction: 0.167
total value: 56.0

按执行顺序理解

1. 按价值除重量排序，不只看其中一项。

2. 取整件重与剩余容量中较小者。

3. 按比例计价值，容量到零就停止。

逐步读懂代码

lambda 是小函数，读取元组位置 2、1 并用价值除重量。reverse=True 让密度最大在前，min 取整件重与剩余容量中较小者。

比例缩放整件价值，减 taken_weight 保持 remaining 为未用容量。仅显示的比例取舍，内部仍算 1/6。容量零即停止。排序 O(n log n)，扫描 O(n)，排序副本 O(n) 空间。假设全部价值正，不解不可分背包。

运行一个完整示例 · 02

检查贪心证明在哪里失效

枚举三个不可分物品的八个子集，与密度优先选择比较。

from itertools import product
items = [("A", 3, 5), ("B", 2, 3), ("C", 2, 3)]
capacity = 4
remaining = capacity
greedy = []
for name, weight, value in sorted(items, key=lambda x: x[2] / x[1], reverse=True):
    if weight <= remaining:
        greedy.append(name)
        remaining -= weight
best_value = -1
best_names = []
for mask in product([0, 1], repeat=len(items)):
    weight = sum(take * item[1] for take, item in zip(mask, items))
    value = sum(take * item[2] for take, item in zip(mask, items))
    if weight <= capacity and value > best_value:
        best_value = value
        best_names = [item[0] for take, item in zip(mask, items) if take]
print("density choice:", greedy)
print("best whole items:", best_names)
print("best value:", best_value)

python greedy-fractional-indivisible-knapsack-counterexample.py

density choice: ['A']
best whole items: ['B', 'C']
best value: 6

按执行顺序理解

1. 运行密度规则，但要求选中的物品完整放入。

2. 枚举二进制选择掩码，计算每个子集总重量和价值。

3. 保留最佳可行子集，并与贪心结果比较。

逐步读懂代码

A 的密度 5/3 大于 B、C 的 3/2。选择 A 后容量只剩 1，其他物品都放不下。product 为每件物品生成取或不取的 0/1 决策，zip 将决策与物品配对，求和检查容量和价值。

选择 B、C 恰好占容量 4，价值为 6，超过 A 的 5。当物品不可拆分时，等重量交换未必可行。枚举全部 2^n 个子集证明了这个小反例；每个子集扫描 O(n)，因此时间是 O(n2^n)，不是可扩展的背包求解器。

运行一个完整示例 · 03

贪心失效时：装入不可拆分的科学套件

米娜去科学展，只能携带四单位重量。A 套件重三单位，能帮助五位访客；B、C 各重两单位，各帮助三位。A 的价值密度最高，按密度贪心会先选 A，之后什么也装不下。米娜改选 B 和 C，却能帮助六位。套件不能切开，因此她需要比较完整选择，不能套用只对可分割物品成立的规则。

def knapsack(items, capacity):
    if not isinstance(capacity, int) or capacity < 0:
        raise ValueError("capacity must be a nonnegative integer")
    if any(not isinstance(w, int) or w <= 0 or v < 0 for _, w, v in items):
        raise ValueError("positive integer weights and nonnegative values required")
    n = len(items)
    best = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i, (_, weight, value) in enumerate(items, 1):
        for room in range(capacity + 1):
            best[i][room] = best[i - 1][room]
            if weight <= room:
                take = value + best[i - 1][room - weight]
                best[i][room] = max(best[i][room], take)
    chosen, room = [], capacity
    for i in range(n, 0, -1):
        if best[i][room] != best[i - 1][room]:
            name, weight, _ = items[i - 1]
            chosen.append(name)
            room -= weight
    return best[n][capacity], list(reversed(chosen)), best

items = [("A", 3, 5), ("B", 2, 3), ("C", 2, 3)]
value, chosen, table = knapsack(items, 4)
assert (value, chosen) == (6, ["B", "C"])
assert knapsack(items, 0)[0] == 0
assert knapsack([], 4)[0] == 0
for i, row in enumerate(table):
    print(f"first {i} kits: {row}")
print("selected:", chosen, "value:", value)