Standard ways of traversing a graph, Data Structure & Algorithms

Q. Which are the two standard ways of traversing a graph?  Explain them with an example of each. 

Ans:

 

The two ways of traversing a graph are written below

i. The depth-first traversal     of a graph is same as the depth-first traversal of a tree. Since a graph does not have any root, when we do a depth-first traversal, we must specify the vertex at which to begin. Depth-first traversal of a graph visits a vertex and then recursively visits all the vertices adjacent to that particular node. The catch is that the graph may have cycles, but the traversal must visit each and every vertex at most once. The solution to the trouble is to keep track of the nodes that have been visited, so that the traversal does not undergo the fate of infinite recursion.

ii. The breadth-first traversal     of a graph is same as the breadth-first traversal of the tree. Breadth-first tree traversal first of all visits all the nodes at the  depth zero (which is the root), then it visits all the nodes at depth one, and this process continues. Since a graph does not has root, when we perform a breadth-first traversal, we should specify the vertex at which to start the traversal. Furthermore, we can define the depth of the given vertex to be the length of the shortest path from the starting vertex to the vertex given to us.

Hence, breadth-first traversal first visits the beginning vertex, then all the vertices adjacent to the starting vertex, and the all the vertices adjacent to those, and it continues.

 

Posted Date: 7/10/2012 6:01:03 AM | Location : United States







Related Discussions:- Standard ways of traversing a graph, Assignment Help, Ask Question on Standard ways of traversing a graph, Get Answer, Expert's Help, Standard ways of traversing a graph Discussions

Write discussion on Standard ways of traversing a graph
Your posts are moderated
Related Questions
A Red-Black Tree (RBT) is a type of Binary Search tree with one extra bit of storage per node, i.e. its color that can either be red or black. Now the nodes can have any of the col

What is Keyed Access- Container A collection may allow its elements to be accessed by keys. For instance, maps are unstructured containers which allows their elements to be

You will write functions for both addition and subtraction of two numbers encoded in your data structure. These functions should not be hard to write. Remember how you add and subt

A tree is a non-empty set one component of which is designated the root of the tree while the remaining components are partitioned into non-empty groups each of which is a subtree

Explain Floyd's algorithm It is convenient to record the lengths of shortest paths in an n by n matrix D known as the  distance matrix: the element d ij   in the i th   row an

In the present scenario of global warming, the computer hard ware and software are also contributing for the increase in the temperature in the environment and contributing for the

Data type An implementation of an abstract data type on a computer. Therefore, for instance, Boolean ADT is implemented as the Boolean type in Java, and bool type in C++;

Consider the file " search_2013 ". This is a text file containingsearch key values; each entry is a particular ID (in the schema given above). You are tosimulate searching over a h

Algorithm for insertion of any element into the circular queue: Step-1: If "rear" of the queue is pointing at the last position then go to step-2 or else Step-3 Step-2: make

Best - Fit Method: - This method obtains the smallest free block whose  size is greater than or equal to get such a block by traversing the whole free list follows.