Algorithms on Graphs

1) DFS
Remember its recursive

2) BFS
Queue based

3) Shortest Path in unweighted graph.

4) Shortest Path in weighted graph.

5) Determine if directed graph has a cycle
Karumanchi , pg 236

If a node is seen a second time before all of its descendants are visited then there is a cycle.

Detect Cycle(G) {
  Initialize Visited array and Predecessor array; 
  call HasCycle
}

HasCycle(G, u) {
 Visited[u] = true; 
 Loop i over all vertices v
   Check if edge present in Adjacency Matrix 
      If Predecessor P[i] != u and Visited[u] then 
          Cycle exists; 
}