Graph Search

Goals

• Find everything findable from a given start vertex.
• Don't explore anything twice.
• Run time - O(m+n) time; this is linear w.r.t. the size of the graph.

Generic Algorithm 

Given graph G, vertex S

- initially s explored, all other vertices unexplored. [1 boolean per node]

- while possible:

  - choose an edge (u,v) with u explored and v unexplored   [If none, halt]

  - mark v explored

Breadth-First Search (BFS)

O(m+n) time using a Queue (FIFO)

1. explore nodes in layers - if there is a path BFS will find it.
2. can compute shortest paths
3. can compute connected components of an undirected graph

For shortest path calculation -> changes to the alg.

initialize dist(v) [0, if v==s, something if v != s]

- when considering edge (v,w):

  - if w unexplored, then set dist(w) = dist(v) + 1

For computing connected components:

Applications: To check if a network is disconnected, graph visualization, clustering.

Input: List of all nodes along with the list of nodes each one is connected to.

- Initially all nodes are unexplored, assume nodes are labelled 1 to n

- for i=1 to n:

  - if i not yet explored in some previous BFS

    - BFS(G, i)  -> discovers connected components..

Depth-First Search (DFS)

O(m+n) time using a stack (LIFO or via recursion)

1. explore aggressively like a maze, backtrack only when neccessary
2. compute topological ordering of directed acyclic graph
3. compute connected components in directed graphs.

Stack version:
mimic BFS code, use stack (push, pop) instead of queue (+minor other modifications)

Recursive version (elegant):

DFS (graph G, start vertex s)

- mark s as explored

- for every edge (s,v):

  - if v unexplored

    - DFS (G,v)