--- date: '2024-02-26' description: Graph representations and traversal, with the invariants behind DFS, BFS, connected components, two-colouring and unweighted shortest paths. id: Graphs modified: 2026-10-12 09:12:00 GMT-04:00 seealso: - '[[thoughts/university/twenty-three-twenty-four/sfwr-2c03/elementary-graph-algorithm.pdf|slides]]' tags: - sfwr2c03 title: Graphs created: '2024-02-26' published: '2024-02-26' pageLayout: default slug: thoughts/university/twenty-three-twenty-four/sfwr-2c03/Graphs permalink: https://aarnphm.xyz/thoughts/university/twenty-three-twenty-four/sfwr-2c03/Graphs.md generator: quartz: v4.6.0 hostedProvider: Cloudflare baseUrl: aarnphm.xyz full: https://aarnphm.xyz/llms-full.txt --- A graph records which objects are related. Vertices can carry data, and edges encode the relation we chose to study. That choice determines what [[thoughts/Information Theory|information]] the graph retains. A road graph might use intersections as vertices and road segments as edges. Write $G = (\mathcal{N}, \mathcal{E})$, with $N = |\mathcal{N}|$ vertices and $M = |\mathcal{E}|$ edges. The definitions below use finite graphs without parallel edges; the undirected examples also exclude self-loops. ## Directed acyclic graph (DAG) A DAG is a directed graph with no directed cycle. It admits a _topological ordering_: every edge points from an earlier vertex to a later one. This is useful for prerequisites, since a cycle would require a task to precede itself. A DAG can still have several paths between two vertices and can be disconnected.[^topological] Application: [[thoughts/Merkle DAG|Merkle DAG]]. ## undirected. > \[!note\] `G = (\mathcal{N}, \mathcal{E})` > > An undirected edge is an unordered pair $\{u,v\}$ of distinct vertices: > > $\mathcal{E} \subseteq \bigl\{\{u,v\}: u,v \in \mathcal{N},\ u \neq v\bigr\}.$ > > The edge can be followed in either direction. A _path_ here is a sequence of distinct vertices with an edge between each consecutive pair. Its length is its number of edges. A _walk_ may repeat vertices and edges. The path containing only one vertex has length zero. A graph is **connected** if every pair of vertices has a path between them. A connected component is a maximal set of mutually reachable vertices; an isolated vertex forms its own component. A weighted graph also assigns a value to each edge: $w: \mathcal{E} \to \mathbb{R}.$ The meaning and allowed signs of those weights depend on the problem. Distance, travel time and cost impose different assumptions. See also [[thoughts/Group theory#Graph isomorphism|Graph isomorphism]]. ## directed. > \[!note\] `G = (\mathcal{N}, \mathcal{E})` > > A directed edge is an ordered pair: > > $\mathcal{E} \subseteq \mathcal{N} \times \mathcal{N}.$ > > The edge $(u,v)$ goes from $u$ to $v$. It says nothing about whether $(v,u)$ exists. > \[!tip\] _path_ difference > > A directed path follows every edge in its specified direction. Reachability can therefore be one-way. > \[!note\] _cycle_ > > A directed cycle follows one or more edges back to its starting vertex, with no other repeated vertex. A self-loop is a cycle of length one. Two vertices are **strongly connected** if each is reachable from the other. A **strongly connected component** is a maximal set with this property. Ignoring edge directions instead gives the _weakly connected_ components. Ordinary DFS from one vertex computes its reachable set; that set need not be a strongly connected component.[^scc] ## matrix [[thoughts/representations|representation]] Assign each vertex a unique index with a bijection $\operatorname{id}: \mathcal{N} \to \{0,\ldots,N-1\}.$ The adjacency matrix $A \in \{0,1\}^{N\times N}$ of a directed graph has entries $$ A[\operatorname{id}(u),\operatorname{id}(v)] = \begin{cases} 1 & \text{if } (u,v) \in \mathcal{E},\\ 0 & \text{otherwise.} \end{cases} $$ For an undirected graph, use $\{u,v\} \in \mathcal{E}$ in the condition, so $A$ is symmetric. A weighted matrix stores weights together with an absence marker; zero cannot mean “no edge” if zero-weight edges are allowed. A conventional matrix stores $\Theta(N^2)$ entries. Edge lookup and update take $\Theta(1)$ time. Listing a vertex’s neighbors requires scanning a row, taking $\Theta(N)$ time even when the vertex has few neighbors.[^matrix] ## The adjacency list representation Store an array $L[0,\ldots,N-1]$ of neighbor lists. For a directed edge $(u,v)$, put $v$ in $L[\operatorname{id}(u)]$. For an undirected edge $\{u,v\}$, put each endpoint in the other’s list. Write $\operatorname{Adj}(u)$ for that list in the algorithms below. The lists store $M$ directed entries or $2M$ undirected entries, plus one list header per vertex. Total storage is $\Theta(N+M)$.[^graph] Assume outgoing lists are unsorted linked lists, insertion prepends a node, and vertex indices are already known. Let $d^+(u)$ be the outdegree. These are worst-case costs, including the constant cost of inspecting an empty list.[^lists] | operation | time | | ---------------------------------------------------------- | ------------------ | | Insert $(u,v)$ when absence is already known | $\Theta(1)$ | | Check for $(u,v)$, or remove it by endpoints | $\Theta(1+d^+(u))$ | | List all outgoing edges of $u$ | $\Theta(1+d^+(u))$ | | List incoming edges by scanning every outgoing list | $\Theta(N+M)$ | | Find the weight of $(u,v)$, or update it by endpoints | $\Theta(1+d^+(u))$ | | Read or update a weight through an existing edge reference | $\Theta(1)$ | If insertion must reject duplicates, it first pays for lookup. An incoming-list index makes incoming traversal proportional to indegree, at the cost of maintaining both directions. Vertex insertion depends on how the outer array grows. Removing a vertex must also remove its incident edges; a full scan of outgoing lists takes $\Theta(N+M)$. ## comparison. For a family of simple graphs, _dense_ usually means $M=\Theta(N^2)$, while _sparse_ often means $M=O(N)$. Usage varies, so state the bound when it matters. Lists save space on sparse graphs. A matrix provides constant-time edge membership tests at the cost of allocating an entry for every vertex pair. ## Traversing undirected graph. DFS and BFS discover vertices reachable from a source $s$. Both must record a discovery before exploring onward, so a cycle cannot keep rediscovering the same vertex. For a small example, take $$ \mathcal{N}=\{a,b,c,d,e\},\qquad \mathcal{E}=\bigl\{\{a,b\},\{a,c\},\{b,d\},\{c,d\}\bigr\}. $$ Starting from $a$, either search reaches $a,b,c,d$. Vertex $e$ stays unreachable. We will inspect neighbors alphabetically when describing a particular visit order. ### Depth-first search (DFS) DFS follows an unvisited neighbor recursively, then returns to inspect the remaining neighbors. Marking on entry prevents the undirected edge back to the parent from starting another recursive call.[^dfs] ```jsx imports={Zoomable,GraphTraversal} ```
"\\begin{algorithm}\n\\caption{DFS-R(G, marked, n)}\n\\begin{algorithmic}\n\\REQUIRE $G = (\\mathcal{N}, \\mathcal{E}), \\text{marked}, n \\in \\mathcal{N}$\n\\STATE $\\text{marked}[n] \\coloneqq \\text{true}$\n\\FORALL{$m \\in \\operatorname{Adj}(n)$}\n \\IF{$\\neg \\text{marked}[m]$}\n \\STATE $\\text{DFS-R}(G, \\text{marked}, m)$\n \\ENDIF\n\\ENDFOR\n\\end{algorithmic}\n\\end{algorithm}"

Algorithm 1 DFS-R(G, marked, n)

Require: G=(N,E),marked,n∈NG = (\mathcal{N}, \mathcal{E}), \text{marked}, n \in \mathcal{N}

1:marked[n]≔true\text{marked}[n] \coloneqq \text{true}

2:for all m∈Adj⁡(n)m \in \operatorname{Adj}(n) do

3:if ¬marked[m]\neg \text{marked}[m] then

4:DFS-R(G,marked,m)\text{DFS-R}(G, \text{marked}, m)

5:end if

6:end for

Initialize every vertex as unmarked, then call the procedure on the source: $$ \text{marked} \coloneqq \{n \mapsto \text{false} \mid n \in \mathcal{N}\}, \qquad \text{DFS-R}(G,\text{marked},s). $$ > \[!tip\] Conclusion > > On return, a vertex is marked exactly when it is reachable from $s$. In the small example, the discovery order is $a,b,d,c$. Changing neighbor order can change the DFS tree and visit order; the reachable set stays the same. The graph is disconnected because $e$ is unmarked. #### Complexity The marked array takes $\Theta(N)$ space. The recursion stack has depth at most $N$, so auxiliary space is $O(N)$. A long path can exhaust a language runtime’s call stack; an explicit stack avoids that recursion limit. Let $R$ be the reachable vertices and $M_R$ the edges in their connected component. Initialization and traversal take $\Theta(N+M_R)$ time: every reached vertex is entered once, and each undirected edge is inspected twice, once from each endpoint. The worst case is $\Theta(N+M)$. This bound assumes adjacency lists; scanning matrix rows gives a worst-case bound of $\Theta(N^2)$. #### Connected-components Start a new DFS at each still-unlabelled vertex. Give it a new component label and pass that label to every vertex it reaches. The outer loop includes isolated vertices.[^cc]
"\\begin{algorithm}\n\\caption{DFS-CC-R(G, cc, n)}\n\\begin{algorithmic}\n\\REQUIRE $G = (\\mathcal{N}, \\mathcal{E}), cc[n] \\neq \\text{unmarked}$\n\\FORALL{$m \\in \\operatorname{Adj}(n)$}\n \\IF{$cc[m] = \\text{unmarked}$}\n \\STATE $cc[m] \\coloneqq cc[n]$\n \\STATE $\\text{DFS-CC-R}(G, cc, m)$\n \\ENDIF\n\\ENDFOR\n\\end{algorithmic}\n\\end{algorithm}"

Algorithm 2 DFS-CC-R(G, cc, n)

Require: G=(N,E),cc[n]≠unmarkedG = (\mathcal{N}, \mathcal{E}), cc[n] \neq \text{unmarked}

1:for all m∈Adj⁡(n)m \in \operatorname{Adj}(n) do

2:if cc[m]=unmarkedcc[m] = \text{unmarked} then

3:cc[m]≔cc[n]cc[m] \coloneqq cc[n]

4:DFS-CC-R(G,cc,m)\text{DFS-CC-R}(G, cc, m)

5:end if

6:end for

"\\begin{algorithm}\n\\caption{COMPONENTS(G)}\n\\begin{algorithmic}\n\\REQUIRE $G = (\\mathcal{N}, \\mathcal{E})$\n\\STATE $cc \\coloneqq \\{ n \\mapsto \\text{unmarked} \\mid n \\in \\mathcal{N} \\}$\n\\FORALL{$n \\in \\mathcal{N}$}\n \\IF{$cc[n] = \\text{unmarked}$}\n \\STATE $cc[n] \\coloneqq n$\n \\STATE $\\text{DFS-CC-R}(G, cc, n)$\n \\ENDIF\n\\ENDFOR\n\\RETURN $cc$\n\\end{algorithmic}\n\\end{algorithm}"

Algorithm 3 COMPONENTS(G)

Require: G=(N,E)G = (\mathcal{N}, \mathcal{E})

1:cc≔{n↦unmarked∣n∈N}cc \coloneqq \{ n \mapsto \text{unmarked} \mid n \in \mathcal{N} \}

2:for all n∈Nn \in \mathcal{N} do

3:if cc[n]=unmarkedcc[n] = \text{unmarked} then

4:cc[n]≔ncc[n] \coloneqq n

5:DFS-CC-R(G,cc,n)\text{DFS-CC-R}(G, cc, n)

6:end if

7:end for

8:return cccc

Each vertex is labelled once across all calls, giving $\Theta(N+M)$ time and $O(N)$ auxiliary space. The example has components $\{a,b,c,d\}$ and $\{e\}$. Two vertices are connected exactly when their labels agree. This procedure is for undirected components; following directed edges this way does not compute strongly connected components. #### Two-colourability > \[!tip\] Bipartite graph > > A graph is _bipartite_ if its vertices can be partitioned into two sets with every edge joining different sets. Either set may be empty. Use colours $1$ and $-1$, reserving $0$ for uncoloured vertices. Each newly reached vertex gets the opposite colour from its parent. An edge joining equal colours proves that the current component cannot be two-coloured; return that failure through every recursive caller.[^bipartite]
"\\begin{algorithm}\n\\caption{DFS-TC-R(G, colors, n)}\n\\begin{algorithmic}\n\\REQUIRE $G = (\\mathcal{N}, \\mathcal{E}), \\text{colors}[n] \\neq 0$\n\\FORALL{$m \\in \\operatorname{Adj}(n)$}\n \\IF{$\\text{colors}[m] = 0$}\n \\STATE $\\text{colors}[m] \\coloneqq -\\text{colors}[n]$\n \\IF{$\\neg \\text{DFS-TC-R}(G, \\text{colors}, m)$}\n \\RETURN $\\text{false}$\n \\ENDIF\n \\ELSIF{$\\text{colors}[m] = \\text{colors}[n]$}\n \\RETURN $\\text{false}$\n \\ENDIF\n\\ENDFOR\n\\RETURN $\\text{true}$\n\\end{algorithmic}\n\\end{algorithm}"

Algorithm 4 DFS-TC-R(G, colors, n)

Require: G=(N,E),colors[n]≠0G = (\mathcal{N}, \mathcal{E}), \text{colors}[n] \neq 0

1:for all m∈Adj⁡(n)m \in \operatorname{Adj}(n) do

2:if colors[m]=0\text{colors}[m] = 0 then

3:colors[m]≔−colors[n]\text{colors}[m] \coloneqq -\text{colors}[n]

4:if ¬DFS-TC-R(G,colors,m)\neg \text{DFS-TC-R}(G, \text{colors}, m) then

5:return false\text{false}

6:end if

7:else if colors[m]=colors[n]\text{colors}[m] = \text{colors}[n] then

8:return false\text{false}

9:end if

10:end for

11:return true\text{true}

"\\begin{algorithm}\n\\caption{TwoColors(G)}\n\\begin{algorithmic}\n\\REQUIRE $G = (\\mathcal{N}, \\mathcal{E})$\n\\STATE $\\text{colors} \\coloneqq \\{ n \\mapsto 0 \\mid n \\in \\mathcal{N} \\}$\n\\FORALL{$n \\in \\mathcal{N}$}\n \\IF{$\\text{colors}[n] = 0$}\n \\STATE $\\text{colors}[n] \\coloneqq 1$\n \\IF{$\\neg \\text{DFS-TC-R}(G, \\text{colors}, n)$}\n \\RETURN $\\text{false}$\n \\ENDIF\n \\ENDIF\n\\ENDFOR\n\\RETURN $\\text{true}$\n\\end{algorithmic}\n\\end{algorithm}"

Algorithm 5 TwoColors(G)

Require: G=(N,E)G = (\mathcal{N}, \mathcal{E})

1:colors≔{n↦0∣n∈N}\text{colors} \coloneqq \{ n \mapsto 0 \mid n \in \mathcal{N} \}

2:for all n∈Nn \in \mathcal{N} do

3:if colors[n]=0\text{colors}[n] = 0 then

4:colors[n]≔1\text{colors}[n] \coloneqq 1

5:if ¬DFS-TC-R(G,colors,n)\neg \text{DFS-TC-R}(G, \text{colors}, n) then

6:return false\text{false}

7:end if

8:end if

9:end for

10:return true\text{true}

Colours alternate along a path. An odd cycle would require the starting vertex to receive the opposite of its own colour when the cycle closes. An undirected graph is bipartite exactly when it has no odd cycle. The example admits the partition $\{a,d,e\}$ and $\{b,c\}$; adding $\{b,c\}$ creates the triangle $a,b,c,a$ and makes it fail. The check takes $O(N+M)$ time and $O(N)$ auxiliary space. ### Breadth-first search (BFS) BFS uses a first-in, first-out queue. Mark the source before enqueueing it, and mark each neighbor when it is enqueued. This gives each reached vertex one queue entry.[^bfs]
"\\begin{algorithm}\n\\caption{BFS(G, s)}\n\\begin{algorithmic}\n\\REQUIRE $G = (\\mathcal{N}, \\mathcal{E}), s \\in \\mathcal{N}$\n\\STATE $\\text{marked} \\coloneqq \\{ n \\mapsto (n = s) \\mid n \\in \\mathcal{N} \\}$\n\\STATE $Q \\coloneqq \\text{a queue holding only } s$\n\\WHILE{$\\neg\\text{Empty}(Q)$}\n \\STATE $n \\coloneqq \\text{Dequeue}(Q)$\n \\FORALL{$m \\in \\operatorname{Adj}(n)$}\n \\IF{$\\neg\\text{marked}[m]$}\n \\STATE $\\text{marked}[m] \\coloneqq \\text{true}$\n \\STATE $\\text{Enqueue}(Q, m)$\n \\ENDIF\n \\ENDFOR\n\\ENDWHILE\n\\RETURN $\\text{marked}$\n\\end{algorithmic}\n\\end{algorithm}"

Algorithm 6 BFS(G, s)

Require: G=(N,E),s∈NG = (\mathcal{N}, \mathcal{E}), s \in \mathcal{N}

1:marked≔{n↦(n=s)∣n∈N}\text{marked} \coloneqq \{ n \mapsto (n = s) \mid n \in \mathcal{N} \}

2:Q≔a queue holding only sQ \coloneqq \text{a queue holding only } s

3:while ¬Empty(Q)\neg\text{Empty}(Q) do

4:n≔Dequeue(Q)n \coloneqq \text{Dequeue}(Q)

5:for all m∈Adj⁡(n)m \in \operatorname{Adj}(n) do

6:if ¬marked[m]\neg\text{marked}[m] then

7:marked[m]≔true\text{marked}[m] \coloneqq \text{true}

8:Enqueue(Q,m)\text{Enqueue}(Q, m)

9:end if

10:end for

11:end while

12:return marked\text{marked}

The example is processed in order $a,b,c,d$. All vertices one edge from $a$ leave the queue before any vertex two edges away. BFS has the same worst-case time and auxiliary-space bounds as DFS with adjacency lists. #### Single-source shortest path For an unweighted graph, shortest means fewest edges. BFS reaches vertices in distance layers, so the first discovery of a vertex fixes its shortest distance. A shorter route would have discovered it from an earlier layer.[^bfs]
"\\begin{algorithm}\n\\caption{BFS-SSSP(G, s)}\n\\begin{algorithmic}\n\\REQUIRE $G = (\\mathcal{N}, \\mathcal{E}), s \\in \\mathcal{N}$\n\\STATE $\\text{distance} \\coloneqq \\{ n \\mapsto \\infty \\mid n \\in \\mathcal{N} \\}$\n\\STATE $\\text{parent} \\coloneqq \\{ n \\mapsto \\text{none} \\mid n \\in \\mathcal{N} \\}$\n\\STATE $\\text{distance}[s] \\coloneqq 0$\n\\STATE $Q \\coloneqq \\text{a queue holding only } s$\n\\WHILE{$\\neg\\text{Empty}(Q)$}\n \\STATE $n \\coloneqq \\text{Dequeue}(Q)$\n \\FORALL{$m \\in \\operatorname{Adj}(n)$}\n \\IF{$\\text{distance}[m] = \\infty$}\n \\STATE $\\text{distance}[m] \\coloneqq \\text{distance}[n] + 1$\n \\STATE $\\text{parent}[m] \\coloneqq n$\n \\STATE $\\text{Enqueue}(Q, m)$\n \\ENDIF\n \\ENDFOR\n\\ENDWHILE\n\\RETURN $(\\text{distance},\\text{parent})$\n\\end{algorithmic}\n\\end{algorithm}"

Algorithm 7 BFS-SSSP(G, s)

Require: G=(N,E),s∈NG = (\mathcal{N}, \mathcal{E}), s \in \mathcal{N}

1:distance≔{n↦∞∣n∈N}\text{distance} \coloneqq \{ n \mapsto \infty \mid n \in \mathcal{N} \}

2:parent≔{n↦none∣n∈N}\text{parent} \coloneqq \{ n \mapsto \text{none} \mid n \in \mathcal{N} \}

3:distance[s]≔0\text{distance}[s] \coloneqq 0

4:Q≔a queue holding only sQ \coloneqq \text{a queue holding only } s

5:while ¬Empty(Q)\neg\text{Empty}(Q) do

6:n≔Dequeue(Q)n \coloneqq \text{Dequeue}(Q)

7:for all m∈Adj⁡(n)m \in \operatorname{Adj}(n) do

8:if distance[m]=∞\text{distance}[m] = \infty then

9:distance[m]≔distance[n]+1\text{distance}[m] \coloneqq \text{distance}[n] + 1

10:parent[m]≔n\text{parent}[m] \coloneqq n

11:Enqueue(Q,m)\text{Enqueue}(Q, m)

12:end if

13:end for

14:end while

15:return (distance,parent)(\text{distance},\text{parent})

The example gives distances $0,1,1,2,\infty$ for $a,b,c,d,e$. To recover a path to a reachable target, follow its parent pointers back to $s$, then reverse the sequence. Unreachable vertices retain infinite distance and no parent. Different neighbor orders can select different shortest paths of the same length. This also works on directed graphs when adjacency lists contain outgoing neighbors. Unequal weights need a different algorithm: if a direct edge costs $10$ and a two-edge route costs $1+1=2$, BFS selects the direct edge because it minimizes edge count. [^topological]: Sedgewick and Wayne, [Topological](https://github.com/kevin-wayne/algs4/blob/master/src/main/java/edu/princeton/cs/algs4/Topological.java). [^scc]: Sedgewick and Wayne, [KosarajuSharirSCC](https://github.com/kevin-wayne/algs4/blob/master/src/main/java/edu/princeton/cs/algs4/KosarajuSharirSCC.java), for the definition and a separate SCC algorithm. [^matrix]: Pat Morin, _Open Data Structures_, [adjacency matrices](https://opendatastructures.org/ods-python/12_1_AdjacencyMatrix_Repres.html). [^graph]: Sedgewick and Wayne, [Graph](https://github.com/kevin-wayne/algs4/blob/master/src/main/java/edu/princeton/cs/algs4/Graph.java) and [Digraph](https://github.com/kevin-wayne/algs4/blob/master/src/main/java/edu/princeton/cs/algs4/Digraph.java). [^lists]: Pat Morin, _Open Data Structures_, [adjacency lists](https://opendatastructures.org/ods-python/12_2_AdjacencyLists_Graph_a.html). Operation costs depend on the list implementation and on which indexes are maintained. [^dfs]: Sedgewick and Wayne, [DepthFirstSearch](https://github.com/kevin-wayne/algs4/blob/master/src/main/java/edu/princeton/cs/algs4/DepthFirstSearch.java). [^cc]: Sedgewick and Wayne, [CC](https://github.com/kevin-wayne/algs4/blob/master/src/main/java/edu/princeton/cs/algs4/CC.java). [^bipartite]: Sedgewick and Wayne, [Bipartite](https://github.com/kevin-wayne/algs4/blob/master/src/main/java/edu/princeton/cs/algs4/Bipartite.java). [^bfs]: Sedgewick and Wayne, [BreadthFirstPaths](https://github.com/kevin-wayne/algs4/blob/master/src/main/java/edu/princeton/cs/algs4/BreadthFirstPaths.java).