Depth First Search

Depth First Search focuses on exploring each available path fully before moving onto the next one at a given node.

---

Algorithm: Depth First Search

---

Input: Graph G(V, E)

1. while (there are non-visited nodes)
2. \(\qquad\) Initialise stack S
3. \(\qquad\) Push a non-visited vertex \(v_i\) to S
4. \(\qquad\) Mark \(v_i\) as visited
5. \(\qquad\) while (S is not empty)
6. \(\qquad\) \(\qquad\) Pop \(v_j\) from S
7. \(\qquad\) \(\qquad\) Mark \(v_j\) as visited
8. \(\qquad\) \(\qquad\) Push non-visited vertices adjacent to \(v_j\) to S

---

Iteration	Stack Contents	Traversal Path
0	A
1	C E	A
2	B F D E	A C
3	F D E	A C B
4	D E	A C B F
5	E	A C B F D
6		A C B F D E

To implement DFS, we will use the stacks defined previously.

def depth_first_traversal(g, start_name):
  start_idx = g.node_names[start_name]
  visited = [False] * g.num_nodes
  S = Stack()
  S.push(start_i)
  # Remove the next node from the DS, add all its neighbours and mark the node visited
  while not S.is_empty():
    current_node = S.pop()
    if not visited[current_node]:
      print(g.nodes_names_rev[current_node])
      visited[current_node] = True
      # Adding all neighbours
      current_node = g.nodes[current_node].head.next
      while current_node:
        if not visited[current_node.data]:
          S.push(current_node.data)
        current_node = current_node.next

Now we can test our graph traversal using the airports example:

if __name__ == "__main__":
  # Create a named graph
  airports = Graph()
  # Populate vertices
  airports.add_node("YYZ")
  airports.add_node("YYR")
  airports.add_node("JFK")
  airports.add_node("UOT")
  airports.add_node("LAX")
  airports.add_node("MMG")
  # Connect with edges
  airports.put_edge_name("YYR", "YYZ")
  airports.put_edge_name("YYZ", "YYR")
  airports.put_edge_name("YYZ", "JFK")
  airports.put_edge_name("YYZ", "UOT")
  airports.put_edge_name("JFK", "LAX")
  airports.put_edge_name("LAX", "MMG")

  # Traverse the graph
  depth_first_traversal(airports, "YYR")