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.
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