From Lecture: Graph traversals
Tricolor Algorithm
It is a general model of many graph traversal algorithms.
Invariant: there is no black->white edge
1 | 1. color all nodes white |
At the end of this algorithm, there will be no grey nodes in the graph. All reachable nodes are black, while all unreachable nodes are white.
Properties unique to different tricolor algorithm:
- which successor in which order to color grey?
- whether and when to color g black
BFS
Gray Frontier: FIFO queue
v.distance= length of shortest path from root to v OR infinity if no path yetv.color==blackmeansv.dist!=infinity& v is not in queue
set
v.distance= infinity for all vset
root.distance = 0,queue.push(root)(root.color=gray)```java
while(!frontier.empty()){Node v=frontier.pop(); for (Node v>g) // v is g's successor if(v.dist==infinity){ // v.color==white v.distance = g.distance+1; frontier.push(v); } //g is now black: g.color = black}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
## DFS
- use LIFO stack
- OR use recursion
### Recursion:
```java
/** Effect: mark all nodes black that
are reachable from v on all white paths.
Requires: v is gray. */
void visit(Node g) {
for (Node v>g){
if(v.color==white){
v.color = gray;
visit(v);
}
}
g.color = black;
}
cycle detection: grey -> grey
Therefore, if we reach a gray successor in DFS, we found a cycle
DFS therefore gives linear-time cycle detection
topological sort:
DFS runs in a postorder traversal way: Node finishes after all descendants/dependents finished
toposort = reversal postorder traversal