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

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|³)

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?).