Graph Algorithms

1. Adjacency List Graph construction
2. Adjacency Matrix Graph Construction
3. Awesome code to find all the connected components in a graph - really neat http://algs4.cs.princeton.edu/41undirected/CC.java.html
4. There are three cases that need to be checked for cycles in an undirected graph :
1. Check for self loops
2. Check for parallel edges
3. If a node is not marked in a dfs, go into the dfs
4. If the node is marked, keep tracking the parent node backward, till you reach that node
5. Bipartite graphs
1. Adjacent vertices must have opposite colors. That is the only check that you need and the only condition that a bipartite graph must satisfy. This will imply odd length cycle in the graph does not exit. The dfs function ensures bipartite. In the check function, first we check whether the graph is bipartite or not. If it is not, we then print an odd length cycle in the graph.
6. Study HeapSort from notes and insertion takes place in O(log n) in heaps
7. Heap data structure is the basic of the implementation of priority queues. No need to write code separately. HeapSort code will do.
8. http://algs4.cs.princeton.edu/43mst/LazyPrimMST.java.html
9. http://algs4.cs.princeton.edu/43mst/UF.java.html - study the union find data structure here - only code
10. Before UF code, read the concept - very nicely explained in Wiki http://en.wikipedia.org/wiki/Disjoint-set_data_structure
11. http://algs4.cs.princeton.edu/43mst/KruskalMST.java.html
12. In a disjoint-set forest, the representative of each set is the root of that set's tree. Find follows parent nodes until it reaches the root. Union combines two trees into one by attaching the root of one to the root of the other. One way of implementing these might be:
    

     function MakeSet(x)
         x.parent := x
    

     function Find(x)
         if x.parent == x
            return x
         else
            return Find(x.parent)
    

     function Union(x, y)
         xRoot := Find(x)
         yRoot := Find(y)
         xRoot.parent := yRoot
    

13. Djkstra, bellman ford and Floyd warshall from cormen

Todo :

1. Planarity
2. Biconnected
3. Bridges