--------普林斯顿大学算法公开课笔记
一、Digraph
Directed graph,set of vertices connected pairwise by directed edges.
二、Problems
1. Is there a directed path from s to t?
2. What is the shortest directed path from s to v?
3. Can you draw a digraph that all edges point upward?
4. Is there a directed path between all pairs of vertices?
三、Digraph related algorithm
1. DFS
[idea] To visit a vertex v:
a. mark v as visited
b. recursively visit all unmarked vertices pointing from v
[C++ code] function buildDepthFirstPaths,DFS, showDFPath
[application]
direct solution to simple digraph problems:
a. reachability( find all vertices reachable from s along a directed path)
b. find the path
c. topological sort
d. directed cycle detection
...
basis for solving difficult digraph problems:
a. directed Euler Path
b. strongly-connected components
...
2.BFS
[idea] Put source vertex s onto a FIFO queue,mark s as visited,repeat util the queue is empty:
a. remove the least recently added vertex v
b. for each unmarked vertex pointing from v,add to queue and marked as visited
[C++ code] function buildBreadFirstPaths,showBFPath
3.Topological Sort
[idea] run DFS demo and return vertices in reverse postorder
eg.
[C++ code] function getDepthFirstOrder
[application] Precedence scheduling: given a set of tasks to be complete with precedence constraints, work out the order of the tasks.
5.Kosaraju-Sharir algorithm (work out strong connected components in digraph)
[idea]
a. get digraph G's reverse graph Gr
b. compute reverse postorder in Gr (run DFS)
c. run DFS in G,visiting unmarked vertices in reverse postorder of Gr
eg.
[C++ code] function getSCC
