PYTHON LESSON 099
朋友圈网络
理解图、顶点、边的概念，掌握邻接矩阵与邻接表两种存储方式并会选场合。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- matrix[a][b] = 1 矩阵记边
- adj = [[] for _ in range(n)] 邻接表
- len(adj[i]) 就是 i 的度数
01 · 核心概念
图的定义与存储：邻接矩阵、邻接表
图的定义与存储：邻接矩阵、邻接表：图（Graph）是研究“关系”的结构：顶点（点）是对象，边（线）是关系。好友关系是相互的，叫无向图；关注、订阅是单方向的，叫有向图。本课先用无向图练手。
GESP Python 7 级 · 图的定义及存储流程图是算法的表示方法，不是 Python 语法。
02 · 语法与规则
先记住这 3 条，再开始写程序
matrix[a][b] = 1 矩阵记边先准确读出这条写法的结构与作用。
adj = [[] for _ in range(n)] 邻接表换一组最小数据，手工推演一次结果。
len(adj[i]) 就是 i 的度数再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 朋友圈网络：邻接矩阵 + 邻接表两种存储
n = 5 # 0 到 4 号五位同学
edges = [(0, 1), (0, 2), (1, 2), (2, 3), (3, 4)]
# 存储方式一：邻接矩阵（一张“关系表格”）
matrix = [[0] * n for _ in range(n)]
for a, b in edges:
matrix[a][b] = 1
matrix[b][a] = 1 # 好友是相互的：无向图记两次
# 存储方式二：邻接表（每人一份“好友名单”）
adj = [[] for _ in range(n)]
for a, b in edges:
adj[a].append(b)
adj[b].append(a)
print("邻接矩阵：")
for row in matrix:
print(row)
print("邻接表：")
for i in range(n):
print(i, "号的朋友：", adj[i])
degree = [len(adj[i]) for i in range(n)]
star = degree.index(max(degree))
print("度数：", degree)
print("人气王是", star, "号，有", max(degree), "位朋友")邻接矩阵： [0, 1, 1, 0, 0] [1, 0, 1, 0, 0] [1, 1, 0, 1, 0] [0, 0, 1, 0, 1] [0, 0, 0, 1, 0] 邻接表： 0 号的朋友： [1, 2] 1 号的朋友： [0, 2] 2 号的朋友： [0, 1, 3] 3 号的朋友： [2, 4] 4 号的朋友： [3] 度数： [2, 2, 3, 2, 1] 人气王是 2 号，有 3 位朋友
无向图的邻接矩阵沿主对角线对称；邻接表里每条边会出现两次。
04 · 逐步理解
每一步只解决一个问题
- 01
图 = 顶点 + 边
图（Graph）是研究“关系”的结构：顶点（点）是对象，边（线）是关系。好友关系是相互的，叫无向图；关注、订阅是单方向的，叫有向图。本课先用无向图练手。
- 02
邻接矩阵：一张关系表格
n×n 的表格，matrix[a][b] 为 1 表示 a 和 b 有边。查“某两人是不是好友”一步到位，但要占 n² 个格子：50 人无所谓，10 万人就是 100 亿格——存不下。
matrix = [[0] * n for _ in range(n)] matrix[a][b] = 1 matrix[b][a] = 1 - 03
邻接表：每人一份名单
给每个顶点开一个列表，里面只登记它真正的邻居。总空间是 2m（每条边记两次），边不多的图用它最省地方，遍历某人的所有朋友也最快。
adj = [[] for _ in range(n)] adj[a].append(b) adj[b].append(a) - 04
度数与人气王
一个顶点的度数就是它连着的边数。邻接表里 len(adj[i]) 直接给出度数；max 找最大、index 找位置，人气王立刻现身。注意并列时 index 只返回第一个。
degree = [len(adj[i]) for i in range(n)] star = degree.index(max(degree)) - 05
两种存储怎么选
顶点少（几百以内）、要频繁查“两点间有没有边”——邻接矩阵；顶点多、边相对少（稀疏图）、要遍历邻居——邻接表。竞赛默认答案几乎都是邻接表。
- 06
从一维列表到二维列表
[[0] * n for _ in range(n)] 这种写法里，for _ 表示“重复 n 次，每次新建一行”。千万不能写成 [[0] * n] * n——那样所有行其实是同一行，改一格全列跟着变。
05 · 练习与检验
自己写出来，才算真正学会
- 1运行程序，对比两种存储的输出
- 2加一条新的好友关系，两种存储都更新
- 3找出没有朋友的“独行侠”
- 4说说 50 人班级和 10 万用户平台各该用哪种存储
06 · 完整知识
继续理解定义、规则和适用边界
第一次学习先完成上面的六个步骤；需要查定义、核对规则、分析误区或理解“为什么”时，再展开对应知识章。
Python 基础条件、循环与程序流程准确理解 if、for、while、range、break、continue 和循环嵌套，而不是背代码模板。＋
正式定义
控制流决定下一条要执行的语句。分支依据布尔条件选择路径；循环在满足规则时重复执行代码块。Python 用冒号和缩进界定代码块。
必须掌握
- if/elif/else 从上到下判断，只执行第一个为真的分支；else 不写条件。
- for 依次取得可迭代对象中的元素；range(start, stop, step) 包含 start、不包含 stop，step 不能为 0。
- while 在每轮开始前检查条件；循环体必须让状态向终止条件推进。
- break 结束最内层循环，continue 跳过本轮剩余语句，循环的 else 仅在没有被 break 终止时执行。
- 嵌套循环的总执行次数通常需要把各层次数相乘；内层 break 不会结束外层循环。
- 边界测试至少覆盖空范围、单个元素、第一项命中、最后一项命中和始终不命中。
常见误区
- range 的右端点多算或少算一次
- while 忘记更新状态造成死循环
- 把两个互斥条件写成两个独立 if
- 误以为 break 会跳出所有嵌套循环
适用边界
- 流程图是算法的表示方法，不是 Python 语法。
- 递归也能表达重复，但有调用开销和递归深度限制，不能无条件代替循环。
核心数据结构树、图、DFS、BFS 与最短路从节点与边的模型出发，掌握遍历、连通性、树结构、最小生成树和最短路径的适用条件。＋
正式定义
图由顶点和边构成；树是连通且无环的无向图。DFS 沿路径深入后回溯，BFS 按距离层次扩展。算法的正确选择取决于图是否有向、边权是否为负、是否稠密以及目标是遍历、连通还是最短路。
必须掌握
- 邻接矩阵占 O(V²) 空间，适合稠密图和快速查边；邻接表占 O(V+E)，适合稀疏图。
- DFS 常用递归或显式栈，BFS 使用队列；一般图都必须记录 visited 防止重复和死循环。
- 无权图的 BFS 首次到达即得到最少边数距离，可用 parent 还原路径。
- 树有 V-1 条边且任意两点路径唯一；二叉树前/中/后序描述根的访问时机。
- Dijkstra 只适用于非负边权；Floyd 求所有点对最短路并允许负边，但不能有可达负环。
- Kruskal 按边权排序并用并查集避环，得到连通无向带权图的最小生成树。
常见误区
- 遍历一般图时不记录 visited
- 对负权边使用 Dijkstra
- 混淆最短路径树与最小生成树
- 递归 DFS 忽略深度限制
适用边界
- 有向无环图、拓扑排序、强连通分量和负权最短路是图论后续主题。
- 网格搜索也是图搜索：格子是顶点，可移动关系是边；不要只背二维数组模板。
核心数据结构列表、元组、字典与集合按顺序、可变性、唯一性和查找需求选择容器，并掌握遍历、推导式、排序与复制。＋
正式定义
容器保存多个对象。list 是可变有序序列，tuple 是不可变有序序列，dict 保存唯一键到值的映射，set 保存无序且不重复的可哈希对象。
必须掌握
- list 支持下标、切片、append、extend、insert、pop、remove 与 sort；多数修改方法返回 None。
- tuple 的逗号比括号更关键，单元素元组必须写成 (value,)。
- dict 保持插入顺序；键必须可哈希且唯一，get 可提供缺省值，items 同时遍历键和值。
- set 用于去重与集合运算：| 并、& 交、- 差、^ 对称差；空集合必须写 set()。
- enumerate 同时给出序号和值，zip 并行遍历多个可迭代对象，默认在最短输入处停止。
- 浅复制只复制最外层容器；嵌套可变对象仍可能共享。
常见误区
- 把 list.sort() 的返回值赋回列表
- 遍历 dict 时同时改变其大小
- 用可变 list 当字典键
- 把 set 当成有固定顺序的序列
适用边界
- 大量从队首删除时 list.pop(0) 是 O(n)，应使用 collections.deque。
- 需要有序映射的特殊操作、计数或默认值时可查阅 collections，但先理解基本 dict。
程序组织类、对象、属性与方法理解对象模型和封装边界，用类表达有状态的实体，而不是把所有程序都强行改成类。＋
正式定义
类描述一类对象的数据与行为；实例是类创建的具体对象。实例方法的第一个参数通常命名为 self，用来访问当前实例；__init__ 在实例创建后负责初始化状态。
必须掌握
- 实例属性通常在 __init__ 中通过 self.name = value 建立。
- 实例方法通过 object.method() 调用；Python 会自动把实例绑定给 self。
- 类属性由实例共享，实例属性属于单个对象；同名实例属性会遮蔽类属性。
- __repr__ 面向开发与调试，__str__ 面向用户显示；特殊方法应遵守其协议。
- 继承表达“是一种”关系，组合表达“拥有一个”关系；能用组合清晰表达时不要滥用继承。
- 对象相等默认仍是身份比较；需要按内容相等时要定义相应协议。
常见误区
- 在方法中漏写 self
- 把每个实例独有的可变数据写成类属性
- 只为包装几个无状态函数而建类
- 继承层次过深导致行为难以追踪
适用边界
- 课程使用普通类解释对象模型；dataclass、property、抽象基类和元类是后续工程工具。
- 算法题常用函数和基本容器更直接，不要求为了“面向对象”而增加结构。
完成检查