Graphs (Part 2)

Graph traversals: depth-first and breadth-first search. Using queues. Shortest paths from a given source, Dijkstra's algorithm. Finding connected components. Special case of shortest paths. Minimal spanning tree: Kruskal's algorithm and Prim's algorithm.

Graph Traversal

General case

Vertices can be "white" (not processed yet), "gray" (in the queue) or "black" (processed).
Initially all vertices are white and the queue is empty.
Traversal starts from the source vertex s: s is added to the queue and colored gray.
The following loop is executed until the queue is empty:
vertex v is removed from the queue (choice of v determines the strategy),
v is processed,
v is colored black,
for all w: (v,w) is in E:
if w is white, w is added to the queue and colored gray.

Breadth-first traversal: queue is a FIFO queue, BFS strategy

Depth-first traversal: queue is a LIFO stack, DFS strategy

Problem specific traversal: queue is a dynamic priority queue in Dijkstra's algorithm

Näide
Example: BFS:

   /**
* Traverse the graph breadth-first.
* Execute vertWork (v) for each vertex v.
* @param s source vertex
*/
public void breadthFirst (Vertex s) {
if (getVertexList() == null) return;
if ((!getVertexList().contains (s))|(s.getGraph() != this))
throw new RuntimeException ("wrong argument to traverse!!");
Iterator vit = vertices();
while (vit.hasNext()) {
Vertex v = (Vertex)vit.next();
v.setVInfo (0); // "white"
}
List vq = Collections.synchronizedList (new LinkedList());
vq.add (s);
s.setVInfo (1); // "gray"
while (vq.size() > 0) {
Vertex v = (Vertex)vq.remove (0); // breadth == FIFO
vertWork (v);
v.setVInfo (2); // "black"
Iterator eit = v.outEdges();
while (eit.hasNext()) {
Edge e = (Edge)eit.next();
Vertex w = e.getToVert();
if (w.getVInfo() == 0) {
vq.add (w);
w.setVInfo (1);
}
}
}
}

/** Work to do when traversing the graph */
public void vertWork (Vertex v) {
System.out.print (" " + v.toString());
}

Let the source vertex be s.
Find the shortest paths from s to all reachable vertices (Dijkstra's algorithm).

Example.

   /**
* Shortest paths from a given vertex. Uses Dijkstra's algorithm.
* For each vertex vInfo is length of shortest path from given
* source s and vObject is previous vertex from s to this vertex.
* @param s source vertex
*/
public void shortestPathsFrom (Vertex s) {
if (getVertexList() == null) return;
if ((!getVertexList().contains (s)) | (s.getGraph() != this))
throw new RuntimeException ("wrong argument to Dijkstra!!");
int INFINITY = Integer.MAX_VALUE / 4; // big enough!!!
Iterator vit = vertices();
while (vit.hasNext()) {
Vertex v = (Vertex)vit.next();
v.setVInfo (INFINITY);
v.setVObject (null);
}
s.setVInfo (0);
List vq = Collections.synchronizedList (new LinkedList());
vq.add (s);
while (vq.size() > 0) {
int minLen = INFINITY;
Vertex minVert = null;
Iterator it = vq.iterator();
while (it.hasNext()) {
Vertex v = (Vertex)it.next();
if (v.getVInfo() < minLen) {
minVert = v;
minLen = v.getVInfo();
}
}
if (minVert == null)
throw new RuntimeException ("error in Dijkstra!!");
if (vq.remove (minVert)) {
// minimal element removed from vq
} else
throw new RuntimeException ("error in Dijkstra!!");
it = minVert.outEdges();
while (it.hasNext()) {
Edge e = (Edge)it.next();
int newLen = minLen + e.getEInfo();
Vertex to = e.getToVert();
if (to.getVInfo() == INFINITY) {
vq.add (to);
}
if (newLen < to.getVInfo()) {
to.setVInfo (newLen);
to.setVObject (minVert);
}
}
}
} // end of shortestPathsFrom()


Finding connected components of an undirected graph

For all vertices v find the number of the connected component where v belongs: k(v).
Initially: k(v) = 0 for all vertices v.
Number of current connected component: n = 0.
For all vertices v:

if k(v)==0 then  n=n+1 and enumerate all vertices w which are reachable from v with number n:
k(w)=n.

   /**
    * Enumerate connected components of this undirected graph.
    * For each vertex vInfo is the number of connected component.
    */
   public void connectedComponents() {
      Iterator<Vertex> vit = vertices();
      while (vit.hasNext()) {
         Vertex v = vit.next();
         v.setVInfo (0);
      }
      int n = 0; // number of component
      vit = vertices();
      while (vit.hasNext()) {
         Vertex v = vit.next();
         if (v.getVInfo() == 0) {
            n++;
            enumerate (v, n);
         }
      }
   }

   /**
    * Enumerate all reachable vertices with given number. DFS.
    * @param v source vertex
    * @param n number
    */
   void enumerate (Vertex v, int n) {
      v.setVInfo (n);
      Iterator<Edge> eit = v.outEdges();
      while (eit.hasNext()) {
         Edge e = eit.next();
         Vertex w = e.getToVert();
         if (w.getVInfo() == 0) {
            enumerate (w, n);
         } else;
      }
   }


Complexities

Lengths of shortest paths between all pairs of vertices: Floyd-Warshall algorithm - O(|V|3)

Shortest paths from a given source: Dijkstra's algorithm - O(|V|log|V| + |E|)


Shortest paths in case of equal arclengths

Find a path that has minimum number of arcs from the given source vertex s to all reachable vertices.

Special case of Dijkstra's algorithm (all lengths are equal to one).

BFS traversal, where for all w: (v, w) is in E

previous(w) = v

Breadth first traversal guarantees minimality of the path (Why?).

Spanning tree

    Spanning tree (V,T) of a connected simple graph (V,E) is a connected acyclic graph, where T is a subset of E.
Spanning tree contains all the vertices of the original graph and minimal number of edges to keep the graph connected. Spanning tree is not unique in general.
Let all edges have positive weight. Minimal spanning tree is a spanning tree with minimum sum of weights of edges.

Kruskal's algorithm. Example of a greedy strategy.
Create a list of edges in increasing order of weights. Create a spanning tree starting with all the vertices without any edges initially.
Choose the minimal edge from the list. If it does not create a loop, add it to the spanning tree.
Bottom-up approach starting to create the tree from single nodes up to connected components. Greedy strategy - uses local decision to choose the next step, result is optimal in global scale.

Prim's algorithm: starts BFS  from the source vertex s, similarly to Dijkstra's algorithm.

 

Jaanus Pöial