10.Graphs§

Paths, Cycles

Connected Components

Directed Graph Representation

Undirected Graph Representation

Representation Space Costs

Graph ADT

interface Graph { // Graph class ADT
  // Initialize the graph with some number of vertices
  void init(int n);

  // Return the number of vertices
  int nodeCount();

  // Return the current number of edges
  int edgeCount();

  // Get the value of node with index v
  Object getValue(int v);

  // Set the value of node with index v
  void setValue(int v, Object val);
  
  // Adds a new edge from node v to node w with weight wgt
  void addEdge(int v, int w, int wgt);

  // Get the weight value for an edge
  int weight(int v, int w);

  // Removes the edge from the graph.
  void removeEdge(int v, int w);

  // Returns true iff the graph has the edge
  boolean hasEdge(int v, int w);

  // Returns an array containing the indicies of the neighbors of v
  int[] neighbors(int v);
}

.

.

Visiting Neighbors

  int[] nList = G.neighbors(v);
  for (int i=0; i< nList.length; i++) {
    if (G.getValue(nList[i]) != VISITED) {
      DoSomething();
    }
  }

Graph Traversals

Graph Traversals (2)

static void graphTraverse(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) {
      doTraversal(G, v);
    }
  }
}

Depth First Search (1)

static void DFS(Graph G, int v) {
  PreVisit(G, v);
  G.setValue(v, VISITED);
  int[] nList = G.neighbors(v);
  for (int i=0; i< nList.length; i++) {
    if (G.getValue(nList[i]) != VISITED) {
      DFS(G, nList[i]);
    }
  }
  PostVisit(G, v);
}

Depth First Search (2)

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

Depth First Search (3)

Cost: \(\Theta(|V| + |E|)\).

Breadth First Search (1)

static void BFS(Graph G, int v) {
  LQueue Q = new LQueue(G.nodeCount());
  Q.enqueue(v);
  G.setValue(v, VISITED);
  while (Q.length() > 0) { // Process each vertex on Q
    v = (Integer)Q.dequeue();
    PreVisit(G, v);
    int[] nList = G.neighbors(v);
    for (int i=0; i< nList.length; i++) {
      if (G.getValue(nList[i]) != VISITED) { // Put neighbors on Q
        G.setValue(nList[i], VISITED);
        Q.enqueue(nList[i]);
      }
    }
    PostVisit(G, v);
  }
}

Breadth First Search (3)

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

Topological Sort

Depth-First Topological Sort (1)

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

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

Depth-First Topological Sort (1)

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

.

.

Queue-Based Topsort (1)

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

.

.

Queue-Based Topsort (2)

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

.

.

Shortest Paths Problems

Shortest Paths Definitions

Single-Source Shortest Paths

Dijkstra’s Algorithm Example

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

.

.

Dijkstra’s Implementation

// Compute shortest path distances from s, store them in D
static 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);
      }
    }
  }
}

Implementing minVertex

Approach 1

// Find the unvisited vertex with the smalled distance
static int minVertex(Graph G, int[] D) {
  int v = 0;  // Initialize v to any unvisited vertex;
  for (int i=0; i<G.nodeCount(); i++) {
    if (G.getValue(i) != VISITED) { v = i; break; }
  }
  for (int i=0; i<G.nodeCount(); i++) {  // Now find smallest value
    if ((G.getValue(i) != VISITED) && (D[i] < D[v])) {
      v = i;
    }
  }
  return v;
}

Approach 2

// Dijkstra's shortest-paths: priority queue version
static void DijkstraPQ(Graph G, int s, int[] D) {
  int v;                                 // The current vertex
  KVPair[] E = new KVPair[G.edgeCount()];        // Heap for edges
  E[0] = new KVPair(0, s);               // Initial vertex
  MinHeap H = new MinHeap(E, 1, G.edgeCount());
  for (int i=0; i<G.nodeCount(); i++) {            // Initialize distance
    D[i] = INFINITY;
  }
  D[s] = 0;
  for (int i=0; i<G.nodeCount(); i++) {          // For each vertex

    KVPair temp = (KVPair)(H.removemin());
    if (temp == null) { return; }      // Unreachable nodes exist
    v = (Integer)temp.value();
    
    while (G.getValue(v) == VISITED) {
      temp = (KVPair)(H.removemin());
      if (temp == null) { return; }      // Unreachable nodes exist
      v = (Integer)temp.value();
    }
      
    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))) { // Update D
        D[w] = D[v] + G.weight(v, w);
        H.insert(new KVPair(D[w], w));
      }
    }
  }
}

.

.

All-pairs Shortest Paths (1)

All-pairs Shortest Paths (2)

An example of :math:`k`-paths in Floyd's algorithm

Floyd’s Algorithm

/** Compute all-pairs shortest paths */
static void Floyd(Graph G, int[][] D) {
  for (int i=0; i<G.n(); i++) { // Initialize D with weights
    for (int j=0; j<G.n(); j++) {
      if (G.weight(i, j) != 0) { D[i][j] = G.weight(i, j); }
    }
  }
  for (int k=0; k<G.n(); k++) { // Compute all k paths
    for (int i=0; i<G.n(); i++) {
      for (int j=0; j<G.n(); j++) {
        if ((D[i][k] != Integer.MAX_VALUE) &&
            (D[k][j] != Integer.MAX_VALUE) &&
            (D[i][j] > (D[i][k] + D[k][j])))
            {
          D[i][j] = D[i][k] + D[k][j];
            }
          }
        }
      }
}

Minimal Cost Spanning Trees

MST Example

Prim’s MST Algorithm

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

.

.

Implementation 1

// Compute shortest distances to the MCST, store them in D.
// V[i] will hold the index for the vertex that is i's parent in the MCST
void Prim(Graph G, int s, int[] D, int[] V) {
  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
    if (v != s) { AddEdgetoMST(V[v], v); }
    int[] nList = G.neighbors(v);
    for (int j=0; j<nList.length; j++) {
      int w = nList[j];
      if (D[w] > G.weight(v, w)) {
        D[w] = G.weight(v, w);
        V[w] = v;
      }
    }
  }
}

Alternate Implementation

Kruskal’s MST Algorithm (1)

Kruskal’s MST Algorithm (2)

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

.

.

Kruskal’s MST Algorithm (3)