## Introduction

**Digraph.** Set of vertices connected pairwise by directed edges.

### 有向图常见问题

**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

### Adjacency-lists digraph representation

Maintain vertex-indexed array of lists.

### Adjacency-lists graph representation (review): Java implementation

### Adjacency-lists digraph representation: Java implementation

## digraph search

### Reachability

Problem. Find all vertices reachable from s along a directed path.

### 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.

### Depth-first search demo

To visit a vertex **v** :

- Mark vertex
**v**as visited. - Recursively visit all unmarked vertices pointing from
**v**.

### Depth-first search (in undirected graphs)

Recall code for undirected graphs.

### Depth-first search (in directed graphs)

Code for directed graphs identical to undirected one.

### Depth-first search in digraphs summary

**DFS enables direct solution of simple digraph problems.**

- Reachability.
- Path finding.
- Topological sort.
- Directed cycle detection.

**Basis for solving difficult digraph problems.**

- 2-satisfiability.
- Directed Euler path.
- Strongly-connected components.

### 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.

### Directed breadth-first search demo

Repeat until queue is empty:

- Remove vertex
**v**from queue. - Add to queue all unmarked vertices pointing from
**v**and mark them.

## 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.

**DAG.** Directed acyclic graph.**Topological sort.** Redraw DAG so all edges point upwards.

### Topological sort

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