Graphs and traversal
導入済み
語彙
| English | 意味 |
|---|---|
| adjacency list/əˈdʒeɪsənsi lɪst/ | adjacency list |
| adjacency matrix | adjacency matrix |
English
List or matrix
- A graph $G = (V, E)$: the course graph has $V = \{A \ldots H\}$ ($8$ nodes) and $10$ undirected edges. The adjacency list stores each node's neighbours — $20$ entries for $10$ undirected edges; the adjacency matrix is the $8 \times 8$ grid of $64$ cells, $1$ at an edge.
{exercise:uni-cs0505-storage}
実践
Ten undirected edges need — adjacency-list entries
難易度 1/5 · 100 コイン + 今日初回達成時の小ボーナス
Each undirected edge is stored twice, once per endpoint.
English
Why O(V+E)
- Both traversals mark each node once ($V$ work) and scan each stored edge once ($E$ work): $O(V + E)$ on the course graph. The matrix pays $O(V^2)$ because every row walks all columns, edge or not.
- The list wins on sparse graphs ($E \ll V^2$); the matrix wins when the graph is dense or the question is one cell lookup. Mark nodes visited — the cycle in any real graph loops forever otherwise.
{exercise:uni-cs0505-cost}
実践
BFS on an adjacency matrix costs —
難易度 1/5 · 100 コイン + 今日初回達成時の小ボーナス
Every row walks all V columns, edge or not — the list wins sparse.
English
Two probes
- BFS from $A$ (neighbours alphabetical): layers $A \,|\, B, C \,|\, D, E \,|\, F, G \,|\, H$; the order reads $A, B, C, D, E, F, G, H$, and a node's layer is its shortest unweighted hop count from $A$ — the queue keeps the frontier in arrival order.
- DFS from $A$: $A \to B \to D$; $D$'s next unvisited neighbour $C$; $C \to E \to F \to H$; $H$'s neighbour $G$ closes the walk: $A, B, D, C, E, F, H, G$ — deep with backtracks. BFS answers shortest hops; DFS exposes paths and cycles.
{exercise:uni-cs0505-orders}
実践
BFS from A on the course graph reads —
難易度 1/5 · 100 コイン + 今日初回達成時の小ボーナス
The queue visits layer by layer: A, then B C, then D E, then F G, then H.