- adjacency list representation
- adjacency matrix

$\begin{array}{cc}\hfill & \hfill \begin{array}{ccccc}\hfill 1\hfill & \hfill 2\hfill & \hfill 3\hfill & \hfill 4\hfill & \hfill 5\hfill \end{array}\hfill \\ \hfill \begin{array}{c}\hfill 1\\ \hfill 2\\ \hfill 3\\ \hfill 4\\ \hfill 5\end{array}& \hfill \left(\begin{array}{ccccc}\hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 1\hfill \\ \hfill 1\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 1\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill 1\hfill \\ \hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill \end{array}\right)\hfill \end{array}$ |

These representation techniques can also be used for

$\begin{array}{cc}\hfill & \hfill \begin{array}{ccccc}\hfill 1\hfill & \hfill 2\hfill & \hfill 3\hfill & \hfill 4\hfill & \hfill 5\hfill \end{array}\hfill \\ \hfill \begin{array}{c}\hfill 1\\ \hfill 2\\ \hfill 3\\ \hfill 4\\ \hfill 5\end{array}& \hfill \left(\begin{array}{ccccc}\hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill \\ \hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \end{array}\right)\hfill \end{array}$ |

- Tree edges - edges in the solution forest.
- Back edges - edges of the original graph that connects a vertex to its ancestor in a solution tree.
- Forward edges - edges not in the solution forest that connect a vertex to a decendent in a solution tree.
- Cross edges - all other edges. They can go between vertices in the same solution tree, as long as one vertex is not an ancestor of the other, or they can go between vertices in different solution trees.

BFS $(G,s)$

1foreach vertex $u\in V[G]-\{s\}$

2do$\mathrm{color}[u]$$\leftarrow $WHITE

3 $d[u]$$\leftarrow $$\infty $

4 $p[u]$$\leftarrow $NIL

5 $\mathrm{color}[s]$$\leftarrow $GRAY

6 $d[s]$$\leftarrow $$0$

7 $p[s]$$\leftarrow $NIL

8 $Q$$\leftarrow $$\{s\}$ /*Q always contains the set of GRAY vertices*/

9while$Q\ne \varnothing $

10do$u$$\leftarrow $$\mathrm{head}[Q]$

11foreach $v\in \mathrm{adj}[u]$

12doif$\mathrm{color}[v]=\text{WHITE}$

13then$\mathrm{color}[v]$$\leftarrow $GRAY

14 $d[v]$$\leftarrow $$d[u]+1$

15 $p[v]$$\leftarrow $$u$

16 ENQUEUE $(Q,v)$

17 DEQUEUE $(Q,u)$

18 $\mathrm{color}[u]$$\leftarrow $BLACK

DFS $(G)$

1foreach vertex $u\in V[G]-\{s\}$

2do$\mathrm{color}[u]$$\leftarrow $WHITE

3 $p[u]$$\leftarrow $NIL

4 $\mathrm{count}$$\leftarrow $$0$

5foreach $u\in V[G]$

6doif$\mathrm{color}[u]=\text{WHITE}$

7thenDFS-VISIT $(u)$

DFS-VISIT $(u)$Consider the following undirected graph. In DFS, all vertices are initialised to WHITE, then each one is visited if they are white. Assuming that $V[G]=\{a,b,c,d,e,f,g,h,i\}$, DFS-VISIT is first invoked on $a$. Within DFS-VISIT, $a$ is coloured GRAY, then the vertices adjacent to $a$ are visited recursively if they are WHITE. When all visits are completed, $a$ is coloured BLACK (note that DFS still works if we leave it as GRAY). This results in the visiting order $\{a,b,d,h,g,c,e,f,i\}$.

1 $\mathrm{color}[u]$$\leftarrow $GRAY

2 $d[u]$$\leftarrow $$\mathrm{count}$

3 $\mathrm{count}$$\leftarrow $$\mathrm{count}+1$

4foreach $v\in \mathrm{adj}[u]$

5doif$\mathrm{color}[v]=\text{WHITE}$

6then$p[v]$$\leftarrow $$u$

7 DFS-VISIT $(v)$

8 $\mathrm{color}[u]$$\leftarrow $BLACK

9 $f[u]$$\leftarrow $$\mathrm{count}$

10 $\mathrm{count}$$\leftarrow $$\mathrm{count}+1$

- In any DFS of a (directed or undirected) graph
$G(V,E)$, for any two
vertices
$u$ and
$v$, exactly one of the following three conditions
holds:
- the intervals $[d[u],f[u]]$ and $[d[v],f[v]]$ are entirely disjoint,
- the interval $[d[u],f[u]]$ is contained entirely within the interval $[d[v],f[v]]$, and $u$ is a descendant of $v$ in the DFS tree, or
- the interval $[d[v],f[v]]$ is contained entirely within the interval $[d[u],f[u]]$, and $v$ is a descendant of $u$ in the DFS tree.

- In a DFS forest of a directed or undirected graph $G(V,E)$, vertex $v$ is a descendant of vertex $u$ if and only if at the time $d[u]$ that the search discovers $u$, vertex $v$ can be reached from $u$ along a path consisting entirely of white vertices.
- In a depth-first search of an undirected graph $G$, every edge of $G$ is either a tree edge or a back edge.

- Initialise an empty linked list.
- Execute DFS(G). As each vertex is coloured BLACK, prepend it to the front of the linked list.
- Return the linked list. The rank of each node is its position in the linked list started from the head of the list.

STRONGLY-CONNECTED-COMPONENTS $(G)$The running time of the algorithm is $O(m+n)$. Steps 1 and 3 take $O(m+n)$ time. Step 2 requires $O(m+n)$ time, and Step 4 takes $O(n)$ time. Thus, the algorithm takes $O(m+n)$ time.

1finish-order$\leftarrow $finish order of DFS( $G$)

2 ${G}^{T}$$\leftarrow $transpose of $G$

3dfs-forest$\leftarrow $DFS trees from DFS( ${G}^{T}$)

. visited in reversefinish-order.

4returndfs-forest

. /*each tree in*/dfs-forestis a strongly connected component.

File translated from T

On 31 Mar 2006, 18:12.