Topological Sort

An ordering of vertices such that if there is an edge from $v_i$ to $v_j$, then $v_j$ comes after $v_i$

Simple

• Algoritm
  1. Find any vertex with no incoming edges
  2. Print this vertex then remove it
  3. Repeat until there are no nodes left
• Use a queue to store the vectors with no incoming nodes

void Graph::topsort() { 
	Queue<Vertex> q;
	int counter = 0;
	q.makeEmpty();
 
	for each Vertex v {
		if( v.indegree == 0 )
          q.enqueue( v ); 
	}
 
	while(!q.isEmpty()) {
		Vertex v = q.dequeue( );
        v.topNum = ++counter;  // Assign next number
        for each Vertex w adjacent to v 
			if( --w.indegree == 0 ) q.enqueue( w );
	}
	
	if( counter != NUM_VERTICES ) 
		throw CycleFoundException{ }; 
 
}