此页面需较新浏览器(支持 SharedArrayBuffer)。请升级 Chrome、Edge、Firefox 或 Safari 至最新版本。
图
- 图是由节点(也称为顶点)通过边(连接)组成的集合。
- 图用来给网络建模:朋友关系、城市间的道路、网页之间的链接。
- 树其实是一种特殊的图;一般的图可以有环,每个节点也可以有很多条连接。
表示一个图:邻接表
- 一种常见的方式是邻接表(adjacency list):一个字典,把每个节点映射到它的邻居列表。
graph["A"]就是与A直接相连的节点列表。- 当每个节点只有少量连接时,这种方式很紧凑。
English
# A graph as a dict: each node maps to its list of neighbours
graph = {
"A": ["B", "C"],
"B": ["A"],
"C": ["A"],
}
print(graph["A"]) # ['B', 'C'] -- A connects to B and C
print(graph["B"]) # ['A']
添加一条边
- 在无向(undirected)图里,一条边
A—B是双向的。 - 所以添加它意味着:把
B追加到A的列表里,并且把A追加到B的列表里。 - 如果某个节点是新的,先用一个空列表把它建起来。
English
def add_edge(graph, a, b):
if a not in graph:
graph[a] = []
if b not in graph:
graph[b] = []
graph[a].append(b)
graph[b].append(a)
graph = {}
add_edge(graph, "A", "B")
add_edge(graph, "A", "C")
print(graph) # {'A': ['B', 'C'], 'B': ['A'], 'C': ['A']}
遍历邻居
- 要从一个节点出发探索,你就读出它的邻居列表,逐个访问。
- 不在图里的节点没有邻居 —— 返回一个空列表,而不是报错。
- 这个邻居查找是更大任务(比如搜索整张图)的第一步。
有向 vs 无向
- 在无向图里,一条边是双向的(比如朋友关系)。
- 在有向(directed)图里,一条边只指向一个方向(单行道,或"关注"链接)。
- 对有向边,你只在一个方向上追加。
常见错误
- 图是由边连接的节点;边可以是单向或双向。
- 树是没有环的图——别把两者搞混。
现在轮到你
- 实现邻接表的几个操作:
add_edge、neighbours和count_edges。 - 每个任务都会在一张小图上检查你的函数。
- 按检查答案来测试它。
难度 5/5 · 今日首次完成可获 400 金币及少量额外奖励
Write add_edge(graph, a, b) for an undirected graph stored as a dict of neighbour lists. Append b 到 graph[a] and a 到 graph[b]. If a node is not in the graph yet, give it an empty list [] first. Change the dict in place.
点击“运行”查看此处输出。
难度 5/5 · 今日首次完成可获 400 金币及少量额外奖励
Write neighbours(graph, node) that returns the list of nodes directly connected to node. If node is not in the graph, return an empty list [] (do not raise an error).
点击“运行”查看此处输出。
难度 5/5 · 今日首次完成可获 400 金币及少量额外奖励
Write count_edges(graph) for an undirected graph: count how many edges it has. Add up the lengths of every neighbour list, then divide by 2 (each edge is stored in both nodes' lists). Example: a triangle A–B–C has 3 edges.
点击“运行”查看此处输出。