Depth-First-Search (DFS)

The first kind of visit in a graph is the DFS and its output is:

• Generate a spanning forest;
• Visit every edge and every vertex;
• Determine if the graph is connected;
• Calculate the connected components of the graph.

First Part – First Labeling

The first labeling part will initialize the graph. In a non-directed graph we have these statuses:

• Vertices can be:
  • UNEXPLORED
  • VISITED
• Edges can be:
  • UNEXPLORED
  • DISCOVERY
  • BACK

DFS(Graph G)
  for all u in G.vertices()
    setLabel(u, UNEXPLORED)
  for all e in G.edges()
    setLabel(e, UNEXPLORED)
  for all v in G.vertices()
    DFS(G, v)

Second Part – True Labeling

In the second part we choose visited and discovery edges.

DFS(Graph G, Vertex v)
  setLabel(v, VISITED)
  for e in G.incidentEdges()
    if getLabel(e) == UNEXPLORED
       w = opposite(v, e)
       if getLabel(w) == UNEXPLORED
         setLabel(e, DISCOVERY)
         DFS(G, w)
       else
         setLabel(e, BACK)

Direct Depth First Search (D-DFS)

In a direct graph

• Vertices has two fields:
  • int discovery_label – a progessive number 0, 1, 2 … n (if zero vertex is UNEXPLORED)
  • int leaving_label – a progressive number 0, 1, 2, … n
• Edges can be:
  • UNEXPLORED
  • DISCOVERY/TREE
  • BACK
  • FORWARD
  • CROSS

We also define two methods:

• getNextLLabel – which generate the next leaving_label progessive number;
• getNextDLabel -which generate the next discovery_label progessive number.

D-DFS(Graph G, Vertex v)
  setDiscoveryLabel(v, getNextDLabel())
  for all e in G.outgoingEdgesFrom(v)
    if getLabel(e) == UNEXPLORED
      w = opposite(v, e)
      if getDiscoveryLabel(v) == UNEXPLORED
        setLabel(e, DISCOVERY)
        D-DFS(G, w)
      else if getLeavingLabel(w) == 0
        setLabel(e, BACK)
      else if getLeavingLabel(v) < getLeavingLabel(w)
        setLabel(e, FORWARD)
      else
        setLabel(e, CROSS)
  setLeavingLabel(v, getNextLLabel)

Strong connected di-graphs

A di-graph is connected if for every pair of vertices A and B we have an oriented path from A to B and from B to A.

Connection test algorithm

We can use the just explained D-DFS in order to understand if a graph is connected, we have to follow these steps:

1. D-DFS on a graph G. After that we have every vertex and every label assigned, starting from whatever vertex;
2. Check for UNEXPLORED vertex. If there's even only one vertex labeled UNEXPLORED the graph isn't connected;
3. Transpose the graph to G'. Let's invert every edge orientation to get a transposed graph;
4. D-DFS on G'. Another labeling but now on the transposed graph;
5. Check for UNEXPLORED vertices. As before, if we have no UNEXPLORED vertices the graph G' is connected and at this point even G is connected.

Calculate the connected components algorithm

Suppose we have a not connected graph. If we try to execute the previous algorithm at the step 5. or 2. it ends telling us that the graph is not connected but.. we have a connected component ready! So could try another D-DFS but starting from an unexeplored vertex but how can we choose it?

We have to note somewhere (an array) the leaving order of the vertex because we will start from the last leaved vertext but unexplored!

Breadth-First-Search (BFS)

Let's see the breadth-first-search that it's useful if we have to calculate shortest paths or if we want to visit every discendet of a vertices before go on in the search.

BFS(Graph G, Vertex v)
  setLabel(v, VISITED)
  L[0] <- new empty sequence
  L[0].insertLast(v)
  i <- 0
  while -L[i].isEmpty()
    L[i+1] <- new empty sequence
    for all e in G.incidentEdges(v)
      if getLabel(e) == UNEXPLORED
        w <- opposite(v,e)
        if getLabel(w) == UNEXPLORED
          setLabel(e, DISCOVERY)
          setLabel(w, VISITED)
          L[i+1].insertLast(w)
        else
          setLabel(e, CROSS)
    i <- i+1

Dijkstra's shortest path algorithm

Let's view now a simple example of a Dijkstra's algorithm for finding the shortest path from a vertex.

DijkstraDistances(Graph G, Vertex s)
  Q <- new heap-based priority queue
  for all v in G.vertices()
    if v == s setDistance(v, 0)
    else setDistance(v, infinite)
    l <- Q.insert(getDistance(v), v)
    setLocator(v,l)
    while -Q.isEmpty()
      u <- Q.removeMin()
      for all e in G.incidentVertices(u)
        w <- opposite(e, u)
        r <- getDistance(u) + weight(e)
        if r < getDistance(w)
          setDistance(w, r)
          Q.replaceKey(getLocator(w), r)