Most Important Algorithms of Graph and Tree

Most Important Algorithms of Graph and Tree 

Algorithm: An algorithm is a sequence of computational steps that transforms the input into output.

A)Graph Algorithm
1)Warshall's Algorithm
a)Main aim of Warshall's Algorithm is find path matrix using power of adjacency .
b)Computes the transitive closure of a relation.
2)Breadth First Search(BFS)
a)Use of Queue Data Structure
b)It is like level order traversal of tree
c)Testing a graph of Bipartiteness
d)Find all connected components in a graph
3)Depth First Search(DFS)
a)Use of Stach DS
b)It is like pre order traversal of tree
c)Topological sorting
d)Find Connected components in a graph
e)Solving puzzles such as Mazes


B)Shortest Path Problem
Sum of the weight of included edge in minimum
1)Dijkstra's Algorithm
a)Source to all other vertex
b)Non -ve edge
c)Greedy approach
d)Uses priority queue to store unvisited vertices by distance from s
e)It is generalization of BFS
2)Bellman Ford's
a)No -ve cycle rechable from source vertex
b)It is work for -ve weight
c)Dynamic approach
d)It has more running time than Dijkstra's
3)Floyd's Warshall's
a)Find shortest path b/w all pairs SPP
b)It is also work for -ve weight
c)Graph should not have any -ve cycle
d)Dynamic approach

C)Minimum Spanning Tree
Undirected and connected graph
1)Prim's Algorithm
a)Select any vertex then go min edge
b)No cycle
c)Greedy approach
d)Grow like tree
2)Kruskal's Algorithm
a)Weighted edge are examine in increasing order
b)No cycle
c)Greedy approach
d)Grow like Forest