void topsortDFS(Graph G) {
int v;
for (v=0; v<G.nodeCount(); v++)
G.setValue(v, null); // Initialize
for (v=0; v<G.nodeCount(); v++)
if (G.getValue(v) != VISITED)
tophelp(G, v);
}
void tophelp(Graph G, int v) {
G.setValue(v, VISITED);
int[] nList = G.neighbors(v);
for (int i=0; i< nList.length; i++)
if (G.getValue(nList[i]) != VISITED)
tophelp(G, nList[i]);
printout(v);
}
What is the running time of the DFS-based topological sort alorithm?
void topsortBFS(Graph G) { // Topological sort: Queue
Queue Q = new LQueue(G.nodeCount());
int[] Count = new int[G.nodeCount()];
int[] nList;
int v;
for (v=0; v<G.nodeCount(); v++) Count[v] = 0; // Initialize
for (v=0; v<G.nodeCount(); v++) { // Process every edge
nList = G.neighbors(v);
for (int i=0; i< nList.length; i++)
Count[nList[i]]++; // Add to v's prereq count
}
for (v=0; v<G.nodeCount(); v++) // Initialize Queue
if (Count[v] == 0) // V has no prerequisites
Q.enqueue(v);
while (Q.length() > 0) { // Process the vertices
v = (Integer)Q.dequeue();
printout(v); // PreVisit for Vertex V
nList = G.neighbors(v);
for (int i=0; i< nList.length; i++) {
Count[nList[i]]--; // One less prerequisite
if (Count[nList[i]] == 0) // This vertex is now free
Q.enqueue(nList[i]);
}
}
}
What is the running time of the Queue-based topological sort alorithm?
void Dijkstra(Graph G, int s, int[] D) {
for (int i=0; i<G.nodeCount(); i++) // Initialize
D[i] = INFINITY;
D[s] = 0;
for (int i=0; i<G.nodeCount(); i++) { // Process the vertices
int v = minVertex(G, D); // Find next-closest vertex
G.setValue(v, VISITED);
if (D[v] == INFINITY) return; // Unreachable
int[] nList = G.neighbors(v);
for (int j=0; j<nList.length; j++) {
int w = nList[j];
if (D[w] > (D[v] + G.weight(v, w)))
D[w] = D[v] + G.weight(v, w);
}
}
}