Minimal spinning tree

Prim's algorithm:

Pick a node, find shortest path, until all nodes visited

Matrix: V^2

Ajacent list: VLOGV + ELOGV

Kuruskal algorithm

Pick a shortest path, find next shoretest path, until they connected

O(E*LOGE)

Bellman-Ford (works negative edge weight)

Simple Path, no cycle

O(V * E)

iteration = V - 1

Dijkstra's algorithm:

Pick a node, visited, choose smallest edge from unvisited node.

O(E LOGV)

Numbers of edges:

If |V| = n

Then O <= |E| <= n(n-1) If directed

   O <= \|E\| <= n\(n-1\) / 2 If undirected

No loops

Union & Find (find cycle in undirected graph)

For each edge, make subsets using both the vertices of the edge. If both the vertices are in the same subset, a cycle is found.

DFS (find cycle in undirected graph)

DFS to detect cycle in an undirected graph in O(V+E) time. We do a DFS traversal of the given graph. For every visited vertex ‘v’, if there is an adjacent ‘u’ such that u is already visited and u is not parent of v, then there is a cycle in graph. If we don’t find such an adjacent for any vertex, we say that there is no cycle. The assumption of this approach is that there are no parallel edges between any two vertices.

DFS (find cycle in directed graph)

Depth First Traversal can be used to detect cycle in a Graph. DFS for a connected graph produces a tree. There is a cycle in a graph only if there is a back edge present in the graph. A back edge is an edge that is from a node to itself (selfloop) or one of its ancestor in the tree produced by DFS.

To detect a back edge, we can keep track of vertices currently in recursion stack of function for DFS traversal. If we reach a vertex that is already in the recursion stack, then there is a cycle in the tree. The edge that connects current vertex to the vertex in the recursion stack is back edge. We have used recStack[] array to keep track of vertices in the recursion stack.

WHITE: Vertex is not processed yet. Initially all vertices are WHITE.

GRAY: Vertex is being processed (DFS for this vertex has started, but not finished which means that all 
descendants (ind DFS tree) of this vertex are not processed yet (or this vertex is in function call stack)

BLACK: Vertex and all its descendants are processed. 

While doing DFS, if we encounter an edge from current vertex to a GRAY vertex, 
then this edge is back edge and hence there is a cycle.