Recent Post

Graph Traversals

GRAPH TRAVERSALS

 Depth First Search

Preorder traversal of ordered tree [( O ( n + e ): Average case]
[ O ( n2 ) : Worst case adjacent matrix].
Stack and backtracking technique.Computers the number of paths between two vertices and computing a cycle and to find articulation points.
Bio connected components and strong components.Euler paths and number of connected components and whether the graph is connected or not connected.

Breadth First Search

 Level by level traversal of ordered tree [ O ( n + e )] and Queue and greedy technique. 
Used for topological sort and dijkstra's algorithm and use prim's algorithm.
Whether the graph is connected or not connected.Number of connected  components and transitive closure of a graph.Computing a cycle.

Chaining

(i) Chaining uses linked implementation for hashing .Number of elements mapped to a location = length of the linked list.
(ii)   Complexity of deleting  an element in the chaining = deletion of a node in single linked list.
(iii) The maximum number of comparisons performed for successful search in chaining = size of large linked list.
(iv) There is no overflow problem.Load factor á½± = n/m , where á½±>=0.
Average number of probes (comparisons ) is successful search.




No comments