Graphs · 图
Graphs
- A graph is a set of nodes (also called vertices) joined by edges (connections).
- Graphs model networks: friends, roads between cities, links between web pages.
- A tree is really a special graph; a general graph can have cycles and many links per node.
图
- 图(graph)是一组由边(edge,连接)连起来的节点(node,也叫顶点 vertex)。
- 图用来给网络建模:朋友关系、城市间的道路、网页之间的链接。
- 树其实是一种特殊的图;一般的图可以有环,每个节点也可以有很多条连接。
Representing a graph: adjacency list
- One common way is an adjacency list: a dictionary mapping each node to its list of neighbours.
graph["A"]is the list of nodes directly connected toA.- This is compact when each node has only a few connections.
表示一个图:邻接表
- 一种常见的方式是邻接表(adjacency list):一个字典,把每个节点映射到它的邻居列表。
graph["A"]就是与A直接相连的节点列表。- 当每个节点只有少量连接时,这种方式很紧凑。
# 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']
Adding an edge
- In an undirected graph, an edge
A—Bgoes both ways. - So adding it means appending
BtoA's list andAtoB's list. - If a node is new, start it with an empty list first.
添加一条边
- 在无向(undirected)图里,一条边
A—B是双向的。 - 所以添加它意味着:把
B追加到A的列表里,并且把A追加到B的列表里。 - 如果某个节点是新的,先用一个空列表把它建起来。
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']}
Walking the neighbours
- To explore from a node, you read its neighbour list and visit each one.
- A node that is not in the graph has no neighbours — return an empty list, not an error.
- This neighbour lookup is the first step of bigger jobs like searching the whole graph.
遍历邻居
- 要从一个节点出发探索,你就读出它的邻居列表,逐个访问。
- 不在图里的节点没有邻居 —— 返回一个空列表,而不是报错。
- 这个邻居查找是更大任务(比如搜索整张图)的第一步。
Directed vs undirected
- In an undirected graph an edge works both ways (a friendship).
- In a directed graph an edge points one way only (a one-way street, a "follows" link).
- For directed edges you would append in one direction only.
有向 vs 无向
- 在无向图里,一条边是双向的(比如朋友关系)。
- 在有向(directed)图里,一条边只指向一个方向(单行道,或"关注"链接)。
- 对有向边,你只在一个方向上追加。
Common mistakes
- A graph is nodes joined by edges; an edge can be one-way or two-way.
- A tree is a graph with no cycles — do not confuse the two.
常见错误
- 图是由边连接的节点;边可以是单向或双向。
- 树是没有环的图——别把两者搞混。
Now you try
- Build the adjacency-list operations:
add_edge,neighbours, andcount_edges. - Each task checks your function on a small graph.
- Press Check answer to test it.
现在轮到你
- 实现邻接表的几个操作:
add_edge、neighbours和count_edges。 - 每个任务都会在一张小图上检查你的函数。
- 按检查答案来测试它。
Write add_edge(graph, a, b) for an undirected graph stored as a dict of neighbour lists. Append b to · 到 graph[a] and a to · 到 graph[b]. If a node is not in the graph yet, give it an empty list [] first. Change the dict in place. · 为一个用「邻居列表字典」表示的无向图编写 add_edge(graph, a, b)。把 b 追加到 graph[a],把 a 追加到 graph[b]。如果某个节点还不在图里,先给它一个空列表 []。就地修改这个字典。
Click Run to see the output here. · 点击“运行”查看此处输出。
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). · 编写 neighbours(graph, node),返回与 node 直接相连的节点列表。如果 node 不在图里,返回空列表 [](不要报错)。
Click Run to see the output here. · 点击“运行”查看此处输出。
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. · 为一个无向图编写 count_edges(graph):数它有多少条边。把每个邻居列表的长度加起来,再除以 2(每条边在两个节点的列表里各存了一次)。例如:三角形 A–B–C 有 3 条边。
Click Run to see the output here. · 点击“运行”查看此处输出。