Graph Traversal

From Lecture: Graph traversals

Tricolor Algorithm¶

It is a general model of many graph traversal algorithms.

Invariant: there is no black->white edge

1. color all nodes white
2. color roots gray
3. while(some gray node g){
	color g's white sucessors grey
	if (no more white successors){
		color g black;
	}
}

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:

1. which successor in which order to color grey?
2. 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 yet

• v.color==black means v.dist!=infinity & v is not in queue

1. set v.distance = infinity for all v

2. set root.distance = 0, queue.push(root) (root.color=gray)

3. 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
   }
   

DFS¶

• use LIFO stack
• OR use recursion

Recursion:¶

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