Topological Sort via DFS...

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);
}

Socrative Quiz

What is the running time of the DFS-based topological sort alorithm?

  1. \(\Theta(|E|)\)
  2. \(\Theta(|V|)\)
  3. \(\Theta(|E|^2)\)
  4. \(\Theta(|V|^2)\)
  5. \(\Theta(|V| + |E|)\)
  6. \(\Theta(|V| |E|)\)

Queue Based Topological Sort

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]);
    }
  }
}

Socrative Quiz

What is the running time of the Queue-based topological sort alorithm?

  1. \(\Theta(|E|)\)
  2. \(\Theta(|V|)\)
  3. \(\Theta(|E|^2)\)
  4. \(\Theta(|V|^2)\)
  5. \(\Theta(|V| + |E|)\)
  6. \(\Theta(|V| |E|)\)

Dijkstra's Algorithm

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);
    }
  }
}