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
What is quick sort? Quick sort is a sorting algorithm that uses the idea if split and conquer. This algorithm chooses an element called as pivot element; search its position in

Prepare a GUI called Hotplate GUI that holds a central panel that draws a rectangular grid that represents Element objects which should be held in a 2-dimensional array. The applic

Acyclic Graphs In a directed graph a path is said to form a cycle is there exists a path (A,B,C,.....P) such that A = P. A graph is called acyclic graph if there is no cycle in

Q.1 Compare two functions n 2 and 2 n for various values of n. Determine when second becomes larger than first. Q.2 Why do we use asymptotic notation in the study of algorit

Graph terminologies : Adjacent vertices: Two vertices a & b are said to be adjacent if there is an edge connecting a & b. For instance, in given Figure, vertices 5 & 4 are adj

Define about the Structure - Container - Some containers hold elements in some sort of structure, and some don't. Containers with no structure include bags and sets. Containe

Tree is dynamic data structures. Trees can expand & contract as the program executes and are implemented via pointers. A tree deallocates memory whereas an element is deleted.

In this assignment, you are invited to design and implement a software system for catalogue sale. A catalogue is organised in a tree structure. Each node of the catalogue tree repr

This is a unit of which targeted on the emerging data structures. Red- Black trees, Splay trees, AA-trees & Treaps are introduced. The learner must explore the possibilities of app

Data Structure and Methods: Build an array structure to accomodate at least 10 elements. Provide routines for the following: An initializer. A routine to populate (