Processing math: 100%

10.Graphs§

Created with Raphaël 2.1.2
Created with Raphaël 2.1.2
(a) undirected graph
Created with Raphaël 2.1.2
(b) directed graph
Created with Raphaël 2.1.2
0
1
2
3
4
3
4
3
1
7
1
(c) labeled graph

Paths, Cycles

Created with Raphaël 2.1.2
Created with Raphaël 2.1.2
a
b
c
d
e
av_l1
Created with Raphaël 2.1.2
a
b
c
d
e
av_l1
av_l2
Created with Raphaël 2.1.2
Created with Raphaël 2.1.2
0
1
2
3
4
av_l3
Created with Raphaël 2.1.2
0
1
2
3
4
3
4
3
1
7
1
av_l4
Created with Raphaël 2.1.2
0
1
2
3
4
3
4
3
1
7
1
av_l5

Connected Components

Created with Raphaël 2.1.2
0
1
2
3
4
5
6
7

Directed Graph Representation

Created with Raphaël 2.1.2
Created with Raphaël 2.1.2
0
1
2
3
4
Adjacency Matrix
  1. 1
  2. 1
  1. 1
  1. 1
  1. 1
  1. 1
0 1 2 3 4
0 1 2 3 4
  1. 0
  2. 1
  3. 2
  4. 3
  5. 4
Created with Raphaël 2.1.2
1
4
3
4
2
1
Adjacency List

Undirected Graph Representation

Created with Raphaël 2.1.2
Created with Raphaël 2.1.2
0
1
2
3
4
Adjacency Matrix
  1. 1
  2. 1
  1. 1
  2. 1
  3. 1
  1. 1
  2. 1
  1. 1
  2. 1
  1. 1
  2. 1
  3. 1
0 1 2 3 4
0 1 2 3 4
  1. 0
  2. 1
  3. 2
  4. 3
  5. 4
Created with Raphaël 2.1.2
1
4
Created with Raphaël 2.1.2
0
3
4
Created with Raphaël 2.1.2
3
4
Created with Raphaël 2.1.2
1
2
Created with Raphaël 2.1.2
0
1
2
Adjacency List

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)

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)

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)

Cost: Θ(|V|+|E|).

.

.

Breadth First Search (1)

Breadth First Search (2)

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)

.

.

Topological Sort

Depth-First Topological Sort (1)

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

Depth-First Topological Sort (1)

.

.

Queue-Based Topsort (1)

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)

.

.

Shortest Paths Problems

Shortest Paths Definitions

Single-Source Shortest Paths

Dijkstra’s Algorithm Example

.

.

Dijkstra’s Implementation

// Compute shortest path distances from s, store them in D
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
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
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
    do { KVPair temp = H.removemin();
         if (temp == null) return;       // Unreachable nodes exist
         v = (Integer)temp.value(); } // Get position
      while (G.getValue(v) == VISITED);
    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(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

Created with Raphaël 2.1.2
A
B
C
D
E
F
7
9
5
6
1
2
2
1

Prim’s MST Algorithm

.

.

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)

.

.

Kruskal’s MST Algorithm (3)