Graphs and traversal

Từ vựng

English	Ý nghĩa
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}

Luyện tập

Ten undirected edges need — adjacency-list entries

Độ khó 1/5 · 100 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay

English

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}

Luyện tập

BFS on an adjacency matrix costs —

Độ khó 1/5 · 100 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay

English

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.