Graph Search Introduction

Graph search algorithms are important but lets have some motivations.

Motivation behind graph search

Here are few motivations:

1. Minimal Road network - Are there sufficient roads for people to go from one place to another. Imagine, Haridwar is only connected via Delhi and there is a natural calamity, then one way people can reach there for relief etc is via Delhi, resulting in worst disaster management, but suppose it is connected via many places, sending relief will be easier. Similarly we can have mobile network, checking if one place can be called from one place to other.
2. Fun - Another fun part is like movie network, where actors/actress can be nodes and edges can be if co-stars appearing in some movie (Undirected graph)
3. Driving directions - Taking from 1 place to other. 
4. Formulate a plan based on priorities, you can traverse from 1 sub plan to other (Directed graph as order involved). 
5. Solving the sudoku - Solving the sudoku can be though as directed graph pointing to sub-puzzle which is already solved.(Directed graph as order involved) 
6. Compute the pieces or component of the graph - providing us with clustering, structure of the web graph.

Generic Graph Search

Goals:

1. Find everything findable/searchable from a given start vertex. So suppose we are given following graph, then findable vertices from starting vertices s, are t,v,w. Note that x,y,z are not searchable.
   
   
   
   Similarly for directed graph, we will always traverse from s in forward direction. So for graph below, vertex t is not searchable, as we are not going to traverse backward.
   
   
   
   
2. Don't explore anything twice, so goal is to complete it in O(m+n) or O(|V|+|E|)

Note: Connectivity of the graph matters a lot in these algorithms. As, if there is very less connectivity, |E|<<|V| so time complexity is O(|V|)

Generic Algorithm

Input : We are given graph G, with vertex s

It is nice to think that vertices explored as territory conquered, and we have to conquer other territories.

So, we need some boolean to find out whether we conquered that territory or node or not.

To start with, we have conquered start node s.

while (possible)
{
    choose an edge (u,v) with u explored and v unexplored (select any from adjency list)    

    Mark v explored
}

This algorithm works for both directed and un-directed graph.

Proof - There is no such point which is unexplored. 
Will do later.

Implementation of generic algorithms
There are lots implementation of this generic algorithm. What gives rise to multiple algorithms of this general sort is in the ambiguity in choosing the next edge.

• BFS - Breadth First Search
  --Select All the neighbours of node s the starting node, then we go to neighbours of this new layer we just added.
  --It can help use compute shortest paths
  -- Compute connected components of undirected graph
  -- Queue is used, because we have to use fifo(first in first out) data-structure
  More details - here.
• DFS - Depth First Search
  -- Aggressively like a mate, backtrack only when necessary
  -- Compute topological ordering of directed acyclic graph
  --Compute connected components in directed graph and undirected graph
  -- Uses stack as it uses recursion
  More Details - here.

Time-wise both are very good strategy.