Graphs and traversal

Словарь

English	Значение
adjacency list/əˈdʒeɪsənsi lɪst/	A graph representation storing a list of neighbours for each vertex.
adjacency matrix	A square table recording edges between pairs of graph vertices.

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 монет + небольшой бонус за первое завершение сегодня

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}

Практика

BFS on an adjacency matrix costs —

Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня

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.