# Notes for Algorithms, Part II: Directed Graphs

This is a note for 4.2 Directed Graphs, *Algorithms, Part II*.

## Introduction

### Some digraph problems

- Path. Is there a directed path from $s$ to $t$?
- Shortest path. What is the shortest directed path from $s$ to $t$?
- Topological sort (拓扑排序). Can you draw a digraph so that all edges point upwards?
- Strong connectivity. Is there a directed path between all pairs of vertices?
- Transitive closure. For which vertices $v$ and $w$ is there a path from $v$ to $w$?
- PageRank. What is the importance of a web page?

## Digraph API

$$

\begin{aligned}

\text{public class } &\text{Digraph} \\

&\text{Digraph(int V)} &\text{create an empty digraph with V vertices}\\

&\text{Digraph(In in)} &\text{create a digraph from input stream}\\

\text{void } &\text{addEdge(int v, int w)} &\text{add a directed edge v->w}\\

\text{Iterable<Integer> } &\text{adj(int v)} &\text{vertices pointing from v}\\

\text{int } &\text{V()} &\text{number of vertices}\\

\text{int } &\text{E()} &\text{number of edges}\\

\text{Digraph } &\text{reverse()} &\text{reverse of this digraph}\\

\text{String } &\text{toString()} &\text{string representation}\\

\end{aligned}

$$

## Representations

representation | space | insert edge from v to w | edge from v to w? | iterate over vertices pointing from v? |
---|---|---|---|---|

list of edges | E | 1 | E | E |

adjacency matrix | V^2 | 1* | 1 | V |

adjacency lists | E+V | 1 | outdegree(v) | outdegree(v) |

* disallows parallel edges

### Adjacency-lists digraph representation: Java implementation

1 | public class Digraph { |

## Digraph search

### Depth-first search in digraphs

**Same method as for undirected graphs.**

- Every undirected graph is a digraph (with edges in both directions).
- DFS is a digraph algorithm.

1 | public class DirectedDFS { |

### Reachability application

- Program control-flow program
- Mark-sweep garbage collector (Mark-sweep algorithm. McCarthy, 1960)

## Breadth-first search in digraphs

**Same method as for undirected graphs.**

- Every undirected graph is a digraph (with edges in both directions).
- BFS is a digraph algorithm.

### Multiple-source shortest paths

Given a digraph and a set of source vertices, find shortest path from any vertex in the set to each other vertex.

Use BFS, but initialize by enqueuing all source vertices.

### Breadth-first search in digraphs application: web crawler (网络爬虫)

Goal. Crawl web, starting from some root web page.

Solution. [BFS with implicit digraph]

- Choose root web page as source $s$.
- Maintain a
`Queue`

of websites to explore. - Maintain a
`SET`

of discovered websites. - Dequeue the next website and enqueue websites to which it links (provided you haven't done so before).

...

## Topological sort (拓扑排序)

### Precedence scheduling (优先级调度)

Goal. Given a set of tasks to be completed with precedence constraints, in which order should we schedule the tasks?

Digraph model. vertex = task; edge = precedence constraint.

### Topological sort

DAG. Directed acyclic (非循环的) graph.

Topological sort. Redraw DAG so all edges point upwards.

- Run depth-first search.
- Return vertices in reverse postorder.

1 | public class DepthFirstOrder { |

## Strongly-connected components

Kosaraju-Sharir algorithm:

- Compute reverse postorder in $G^R$.
- Run DFS in $G$, visiting unmarked vertices in reverse postorder of $G^R$.

1 | public class KosarajuSharirSCC { |