Graphs

Basics
Representations
Traversals

Basics

Graph $G$ is an ordered pair $G = \langle V, E \rangle$, where $V$ is a set of nodes or vertices and $E$ is a set of edges.

We assume that $|V| = n$ and $|E| = m$.

Types of graphs

Graphs can be:

Labeled or unlabeled
Directed or undirected
Weighted or unweighted
Simple or non-simple
Connected or disconnected
Cyclic or acyclic
Sparse or dense
Graph or hypergraph

Types of graphs

Relationship between edges and nodes

Assume that there are no duplicate/repeated edges between two nodes. Then the relationship between $m$ and $n$ are shown below.

Graph type	Self-loops not allowed	Self-loops allowed
Directed graph	$m \in [0, n(n-1)]$	$m \in [0, n^2]$
Undirected graph	$m \in [0, n(n-1)/2]$	$m \in [0, n(n+1)/2]$

Representations

Two major types of graph representations:

Adjacency list
Adjacency matrix

Adjacency list

Graph and its adjacency list representation (part a).

Space $= \Theta(|V| + |E|) = \Theta(n + m)$

Adjacency matrix

Graph and its adjacency matrix representation (part a).

Space $= \Theta(|V|^2) = \Theta(n^2)$

Traversals

Traverse a given graph $G = (V, E)$.

Generic algorithm

\begin{algorithm}
\begin{algorithmic}
\FUNCTION{GraphTraversal}{$G = (V,E)$}
\STATE \{ Initially all nodes are unmarked \}
\FOR{each vertex $u \in V$}
    \STATE $u.mark \gets 0$
    \STATE $u.parent \gets null$
\ENDFOR
\STATE{}
\STATE \{ Traverse each connected component if it is not traversed \}
\STATE Global $count \gets 0$
\FOR{each vertex $u \in V$}
    \IF{$u.mark = 0$}
        \STATE \CALL{GraphTraversal}{$u$}
\ENDIF
\ENDFOR
\ENDFUNCTION


\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\FUNCTION{GraphTraversal}{$u$}
\STATE Create a data structure $S$
\STATE $u.parent \gets null$;
 $S.\text{Add}(u)$

\STATE{}
\WHILE{$S$ is not empty}

\STATE \{ Stage 1. Remove \}
\STATE $u \gets S.\text{Remove}()$

\IF{$u.mark = 0$}

\STATE \{ Stage 2. Mark \}
\STATE $count \gets count + 1$; $u.mark \gets count$

\STATE \{ Stage 3. Add children \}
\FOR{each neighbor $v \in \text{Neighbors}(u)$}
\STATE $v.parent \gets u$; $S.\text{Add}(v)$
\ENDFOR
\ENDIF
\ENDWHILE
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Different algorithms

Data structure $S$	Traversal algorithm	Add and Remove
Stack	Depth-first traversal	Push and Pop
Queue	Breadth-first traversal	Enqueue and Dequeue
Priority queue	Best-first traversal	Add and RemoveMin

Complexity

$\text{Adjacency list: }\langle\text{Time, Space}\rangle = \langle |V|+|E| \times T, |V|+|E| \rangle$

$\text{Adjacency matrix: }\langle\text{Time, Space}\rangle = \langle |V|^2 +|E| \times T, |V|^2 \rangle$

$\text{where, } T = \max(\text{time(Add)}, \text{time(Remove)})$

Applications

Depth-first: Exploring one path fully before trying alternatives.
Breadth-first: Checking all immediate options before going deeper.

Feature	Depth-first	Breadth-first
Data structure	Stack	Queue
Recursive	✓, ✗	✗
Finding any path (not shortest)	✓	✗
Finding shortest path (unweighted)	✗	✓
Cycle detection	✓	✓
Topological sorting	✓	✗
Connected components	✓	✓
Backtracking	✓	✗

DFS:

Finding connected components.
Topological sorting.
Finding the bridges of a graph.
Finding strongly connected components.
Determining whether a species is closer to one species or another in a phylogenetic tree.
Planarity testing.
Solving puzzles with only one solution, such as mazes. (DFS can be adapted to find all solutions to a maze by only including nodes on the current path in the visited set.)
Maze generation may use a randomized depth-first search.
Finding biconnectivity in graphs.

BFS:

Finding the shortest path between two nodes $u$ and $v$, with path length measured by number of edges
(Reverse) Cuthill–McKee mesh numbering.
Edmonds-Karp method for computing maximum flow.
Serialization/Deserialization of a binary tree vs serialization in sorted order.
Construction of the failure function of the Aho-Corasick pattern matcher.
Testing bipartiteness of a graph.
Implementing parallel algorithms for computing a graph's transitive closure.

Depth-first search

Nonrecursive algorithm

\begin{algorithm}
\begin{algorithmic}
\FUNCTION{DFS}{$G = (V,E)$}
\FOR{each vertex $u \in V$}
    \STATE $u.mark \gets 0$
    \STATE $u.parent \gets null$
\ENDFOR
\STATE Global $count \gets 0$
\FOR{each vertex $u \in V$}
\IF{$u.mark = 0$}
\STATE \CALL{DFS}{$u$}
\ENDIF
\ENDFOR
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\FUNCTION{DFS}{$u$}
\STATE Create a stack $S$
\STATE $u.parent \gets null$; $S.\text{Push}(u)$
\WHILE{$S$ is not empty}
\STATE \{ Stage 1. Remove \}
\STATE $u \gets S.\text{Pop}()$
\IF{$u.mark = 0$}
\STATE \{ Stage 2. Mark \}
\STATE $count \gets count + 1$; $u.mark \gets count$
\STATE \{ Stage 3. Add children \}
\FOR{each neighbor $v \in \text{Neighbors}(u)$}
\STATE $v.parent \gets u$; $S.\text{Push}(v)$
\ENDFOR
\ENDIF
\ENDWHILE
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Recursive algorithm

\begin{algorithm}
\begin{algorithmic}
\FUNCTION{DFS}{$G = (V,E)$}
\FOR{each vertex $u \in V$}
\STATE $u.mark \gets 0$
\STATE $u.parent \gets null$
\ENDFOR
\STATE Global $count \gets 0$
\FOR{each vertex $u \in V$}
\IF{$u.mark = 0$}
\STATE \CALL{DFS}{$u$}
\ENDIF
\ENDFOR
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\FUNCTION{DFS}{$u$}
\STATE $count \gets count + 1$; $u.mark \gets count$
\FOR{each neighbor $v \in \text{Neighbors}(u)$}
\IF{$v.mark = 0$}
\STATE $v.parent \gets u$
\STATE \CALL{DFS}{$v$}
\ENDIF
\ENDFOR
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Example

Breadth-first search

Nonrecursive algorithm

\begin{algorithm}
\begin{algorithmic}
\FUNCTION{BFS}{$G = (V, E)$}
\FOR{each vertex $u \in V$}
\STATE $u.mark \gets 0$
\STATE $u.parent \gets null$
\ENDFOR
\STATE Global $count \gets 0$
\FOR{each vertex $u \in V$}
\IF{$u.mark = 0$}
\STATE \CALL{BFS}{$u$}
\ENDIF
\ENDFOR
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\FUNCTION{BFS}{$u$}
\STATE Create a queue $Q$
\STATE $u.parent \gets null$; $Q.\text{Enqueue}(u)$

\STATE{}
\WHILE{$Q$ is not empty}
\STATE \{ Stage 1. Remove \}
\STATE $u \gets Q.\text{Dequeue}()$
\IF{$u.mark = 0$}
\STATE \{ Stage 2. Mark \}
\STATE $count \gets count + 1$; $u.mark \gets count$
\STATE \{ Stage 3. Add children \}
\FOR{each neighbor $v \in \text{Neighbors}(u)$}
\STATE $v.parent \gets u$; $Q.\text{Enqueue}(v)$
\ENDFOR
\ENDIF
\ENDWHILE
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Nonrecursive algorithm (improved)

\begin{algorithm}
\begin{algorithmic}
\FUNCTION{BFS}{$G = (V, E)$}
\FOR{each vertex $u \in V$}
\STATE $u.mark \gets 0$
\STATE $u.parent \gets null$
\ENDFOR
\STATE Global $count \gets 0$
\FOR{each vertex $u \in V$}
\IF{$u.mark = 0$}
\STATE \CALL{BFS}{$u$}
\ENDIF
\ENDFOR
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
\FUNCTION{BFS}{$u$}
\STATE Create a queue $Q$
\STATE $count \gets count + 1$; $u.mark \gets count$
\STATE $u.parent \gets null$; $Q.\text{Enqueue}(u)$
\STATE{}
\WHILE{$Q$ is not empty}
\STATE \{ Stage 1. Remove \}
\STATE $u \gets Q.\text{Dequeue}()$

\STATE \{ Stage 2. Mark and add unmarked children \}
\FOR{each neighbor $v \in \text{Neighbors}(u)$}
\IF{$v.mark = 0$}
\STATE $count \gets count + 1$; $v.mark \gets count$
\STATE $v.parent \gets u$; $Q.\text{Enqueue}(v)$
\ENDIF
\ENDFOR
\ENDWHILE
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}