Graphs
Python for A-Level CS Lesson 15 2:12 English narration · English + 中文 subtitles burned in
Chapters
Transcript
A graph is a set of nodes joined by edges.
图是一组由边连接起来的结点。
The circles are the nodes — you will also see them called vertices — and the lines are edges.
那些圆圈是结点——你也会看到它们被叫做顶点—— 而那些线是边。
That is the whole definition, and it is deliberately loose, because a graph can model anything that connects: people in a friendship network, cities joined by roads, pages joined by links.
整个定义就这些，而且它是故意宽松的， 因为图可以给任何"有连接"的东西建模： 朋友网络里的人、被公路连起来的城市、被链接连起来的网页。
Unlike a tree, a graph may loop back on itself.
与树不同，图可以绕回它自己。
To put a graph in code you need a representation, and the common one is an adjacency list: a dictionary in which each node maps to a list of its neighbours.
要把图写进代码，你需要一种表示法， 而最常见的一种是邻接表： 一个字典，其中每个结点映射到它的邻居列表。
Look at A's row.
看 A 那一行。
It reads B and C — and those are exactly the two circles A touches in the picture.
它写着 B 和 C——而这正是图里 A 挨着的那两个圆圈。
The list IS its edges, which is why the dictionary and the drawing are the same object.
那个列表就是它的边， 这就是为什么这个字典和这张图是同一个东西。
Adding an edge is the first task, and it has a catch.
添加一条边是第一道题，而它有个坑。
In an undirected graph the connection works both ways, so one edge is two appends: append B to A's list, and A to B's.
在无向图里，这条连接是双向起作用的， 所以一条边等于两次 append： 把 B 加到 A 的列表里，再把 A 加到 B 的列表里。
Miss the second one and the graph is half-built — A knows about B while B has never heard of A.
漏掉第二次，这个图就只建了一半—— A 知道 B，而 B 从来没听说过 A。
One line on the page, but the graph has to know it from both ends.
纸上是一条线，但这个图必须从两端都知道它。
That both-ways behaviour is a choice, not a law.
那种"双向"的行为是一种选择，不是定律。
An undirected edge is a friendship: if you are my friend, I am yours.
无向边是一段友谊：如果你是我的朋友，我就是你的。
A directed edge points one way only — a one-way street, or a follows link on a social network.
有向边只指向一个方向—— 一条单行道，或者社交网络上的"关注"。
The code difference is exactly one line: for a directed edge you append in one direction and stop.
代码上的区别正好是一行： 对于有向边，你只在一个方向上 append，然后就停。
Four things to take with you.
带走四点。
One: a graph is nodes joined by edges.
第一：图是由边连接起来的结点。
Two: an adjacency list maps each node to its neighbours.
第二：邻接表把每个结点映射到它的邻居。
Three: an undirected edge is appended at both ends.
第三：无向边要在两端都添加。
Four: a node that is not in the graph has no neighbours, which is an empty list and not an error.
第四：不在图里的结点没有邻居， 那是一个空列表，不是一个错误。
Do the three tasks — and that is the course.
做完那三道题——这门课就结束了。