Traversal of graph

 

Graph Traversal - DFS

Graph traversal is a technique used for a searching vertex in a graph. The graph traversal is also used to decide the order of vertices is visited in the search process. A graph traversal finds the edges to be used in the search process without creating loops. That means using graph traversal we visit all the vertices of the graph without getting into looping path.

There are two graph traversal techniques and they are as follows...

  1. DFS (Depth First Search)
  2. BFS (Breadth First Search)

DFS (Depth First Search)

DFS traversal of a graph produces a spanning tree as final result. Spanning Tree is a graph without loops. We use Stack data structure with maximum size of total number of vertices in the graph to implement DFS traversal.

We use the following steps to implement DFS traversal...

  • Step 1 - Define a Stack of size total number of vertices in the graph.
  • Step 2 - Select any vertex as starting point for traversal. Visit that vertex and push it on to the Stack.
  • Step 3 - Visit any one of the non-visited adjacent vertices of a vertex which is at the top of stack and push it on to the stack.
  • Step 4 - Repeat step 3 until there is no new vertex to be visited from the vertex which is at the top of the stack.
  • Step 5 - When there is no new vertex to visit then use back tracking and pop one vertex from the stack.
  • Step 6 - Repeat steps 3, 4 and 5 until stack becomes Empty.
  • Step 7 - When stack becomes Empty, then produce final spanning tree by removing unused edges from the graph

Back tracking is coming back to the vertex from which we reached the current vertex.

Example

 


Graph Traversal - BFS

BFS (Breadth First Search)

BFS traversal of a graph produces a spanning tree as final result. Spanning Tree is a graph without loops. We use Queue data structure with maximum size of total number of vertices in the graph to implement BFS traversal.

We use the following steps to implement BFS traversal...

  • Step 1 - Define a Queue of size total number of vertices in the graph.
  • Step 2 - Select any vertex as starting point for traversal. Visit that vertex and insert it into the Queue.
  • Step 3 - Visit all the non-visited adjacent vertices of the vertex which is at front of the Queue and insert them into the Queue.
  • Step 4 - When there is no new vertex to be visited from the vertex which is at front of the Queue then delete that vertex.
  • Step 5 - Repeat steps 3 and 4 until queue becomes empty.
  • Step 6 - When queue becomes empty, then produce final spanning tree by removing unused edges from the graph
Example

Popular posts from this blog

DATA STRUCTURES-II

 UNIT – I  Tree: Header nodes, Threads, Binary search trees, Searching, Insertion and deletion in aBinary search tree , AVL search trees, Insertion and deletion in AVL search tree , m-waysearch tree, Searching, Insertion and deletion in an m-way search tree , B-trees, Searching,Insertion and deletion in a B-tree, B+tree , Huffman’s algorithm , General trees.  UNIT – II  Graphs: Warshall’s algorithm for shortest path , Dijkstra algorithm for shortest path , Operations on graphs , Traversal of graph , Topological sorting .  UNIT – III  Sorting: Internal & external sorting , Radix sort , Quick sort , Heap sort , Merge sort . Searching: Liner search, binary search, merging , Comparison of various sorting and searching algorithms on the basis of their complexity .  UNIT – IV  Files: Physical storage devices and their characteristics , Attributes of a file viz fields, records,Fixed and variable length records, Primary and secondary keys , Clas...
Read more

DATA STRUCTURES FOR BCA

UNIT – I  Introduction: Elementary data organization, Data Structure definition , Data type vs. data structure , Categories of data structures, Data structure operations, Applications of data structures, Algorithms complexity and time-space tradeoff, Big-O notataion.   Strings: Introduction, Storing strings, String operations, Pattern matching algorithms.  UNIT – II  Arrays: Introduction, Linear arrays, Representation of linear array in memory, address calculations, Traversal, Insertions, Deletion in an array, Multidimensional arrays, Parallel arrays, Sparse arrays.  Linked List: Introduction, Array vs. linked list, Representation of linked lists in memory, Traversal, Insertion, Deletion, Searching in a linked list, Header linked list, Circular linked list, Two-way linked list, Threaded lists, Garbage collection, Applications of linked lists.  UNIT – III  Stack: Introduction, Array and linked representation of stacks, Operations on stacks, Ap...
Read more

DATA STRUCTURES FOR B.TECH

DATA STRUCTURES Unit 1: Introduction :   Basic Terminologies:   C oncept of Data Structure, Choice of right Data Structure , Algorithms , how to design and develop algorithm, Complexity of algorithm.   Operations: insertion, deletion, traversal etc,   Analysis of an Algorithm. Searching:  Linear Search and Binary Search Techniques and their complexity analysis. Unit 2: Stacks  and  Queues : Stack  and  its  operations: Algorithms and their complexity analysis, Applications of Stacks: Expression       Conversion and evaluation -corresponding algorithms and complexity analysis. queue, Types of Queue: Simple  Queue, Circular Queue, Priority Queue ; Operations on each types of Queues: Algorithms and their analysis.   Unit 3 : Linked Lists:      Singly   linked  lists: Representation in memory, Algorithms of several operations:...
Read more