图与树
引入| English | 释义 | 拼音 |
|---|---|---|
| graph/ɡræf/ | 图 | tú |
| edge/edʒ/ | 边 | biān |
| degree/dɪˈɡriː/ | 度 | dù |
| directed | 有向 | yǒu xiàng |
| vertex/ˈvɜːteks/ | 顶点 | dǐng diǎn |
| adjacency matrix | 邻接矩阵 | lín jiē jǔ zhèn |
| adjacency list/əˈdʒeɪsənsi lɪst/ | 邻接表 | lín jiē biǎo |
| sparse | 稀疏 | xī shū |
| handshake lemma | 握手引理 | wò shǒu yǐn lǐ |
| tree/triː/ | 树 | shù |
| acyclic | 无环 | wú huán |
| leaf | 叶子 | yè zi |
| breadth-first search/bredθ fɜːst sɜːtʃ/ | 广度优先搜索 | guǎng dù yōu xiān sōu suǒ |
| depth-first search/depθ fɜːst sɜːtʃ/ | 深度优先搜索 | shēn dù yōu xiān sōu suǒ |
Friends, flights and build steps
- A social network, an airline map and the order in which code modules must compile look nothing alike. Each one is a set of things joined by links.
- That shared shape is a graph. Learn it once and the same tools count, search and check all three.
Vertices, edges and degree
- A graph 图 $G = (V, E)$ has vertices 顶点 $V$ and edges 边 $E$ joining pairs of them. Edges can be directed 有向 (one-way, like build order) or undirected (like friendship).
- The degree 度 of a vertex is the number of edges touching it. An isolated vertex has degree 0 and still counts as a vertex.
Match each system to the kind of graph that models it.
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
Friendship runs both ways; build order runs one way and cannot loop; distances are weights; links can point back.
Two ways to store a graph
- An adjacency matrix 邻接矩阵 is an $n \times n$ grid of 0s and 1s. It takes $n^2$ space but answers "is there an edge from $u$ to $v$?" in $O(1)$.
- An adjacency list 邻接表 stores each vertex's neighbours. It takes $O(|V| + |E|)$ space, so it suits sparse 稀疏 graphs with few edges per vertex.
A road map has a million junctions, each joined to about four others. The best storage is —
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
A matrix needs 10¹² cells, almost all 0; a list stores only the 4 million or so edges that exist.
The handshake lemma
- Each edge adds 1 to the degree of each of its two ends, so $\sum_v \deg(v) = 2|E|$. This is the handshake lemma 握手引理. In the figure, $3 + 2 + 2 + 2 + 3 = 12 = 2 \times 6$.
- Corollary: the number of odd-degree vertices is always even. Seven people cannot each shake hands with exactly three others, because $7 \times 3 = 21$ is odd.
A graph has 9 edges. What is the sum of all its vertex degrees?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
Each edge adds 2, so $2 \times 9 = 18$.
A graph can have exactly three vertices of odd degree.
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
The degree sum is even, so the odd degrees must come in an even number.
Trees: connected, no cycles
- A tree 树 is connected (one piece) and acyclic 无环 (no cycles). Every tree with $|V|$ vertices has exactly $|E| = |V| - 1$ edges.
- A leaf 叶子 has degree 1. Combine the two facts with the handshake lemma to answer most tree questions.
A tree has 12 vertices, 5 of them leaves. Edges: $12 - 1 = 11$, so the degree sum is $2 \times 11 = 22$. The leaves give 5, so the other 7 vertices carry $22 - 5 = 17$.
A tree has 30 vertices. How many edges does it have?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
Every tree has $|E| = |V| - 1 = 29$.
Two ways to search
- Breadth-first search 广度优先搜索 (BFS) uses a queue and visits level by level. In an unweighted graph it finds shortest paths, counted in edges.
- Depth-first search 深度优先搜索 (DFS) uses a stack or recursion and goes as deep as it can before backing up. It finds connected pieces and detects cycles.
Which statements about BFS are true? Select all that apply.
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
BFS counts edges, so it gives shortest paths only when every edge costs the same.
Marks that slip away
- Connected is not complete. Connected means one piece; complete means every pair is joined.
- BFS on weighted graphs. BFS counts edges, not weights; a weighted shortest path needs another method.
- Ignoring degree-0 vertices. They still count in $|V|$.
You've got it
- $G = (V, E)$; a matrix costs $n^2$ with $O(1)$ edge tests; a list costs $O(|V| + |E|)$, best for sparse graphs.
- $\sum \deg = 2|E|$, so the number of odd-degree vertices is even.
- Tree: connected and acyclic, $|E| = |V| - 1$. BFS: queue, level order; DFS: stack, depth first.