有向图

发表于   |   分类于

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

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.

Depth-first search order