Standard ways of traversing a graph, Data Structure & Algorithms

Assignment Help:

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.

 


Related Discussions:- Standard ways of traversing a graph

Explain space complexity, Explain Space Complexity Space Complexity :...

Explain Space Complexity Space Complexity :- The space complexity of an algorithm is the amount of memory it requires to run to completion. Some of the reasons to study space

Algorithm, algorithm to search a node in linked list

algorithm to search a node in linked list

What is quick sort, What is quick sort?   Answer Quick sort is on...

What is quick sort?   Answer Quick sort is one of the fastest sorting algorithm used for sorting a list. A pivot point is chosen. Remaining elements are divided or portio

Explain time complexity, Time Complexity, Big O notation The amount of ...

Time Complexity, Big O notation The amount of time needed by an algorithm to run to its completion is referred as time complexity. The asymptotic running time of an algorithm i

User-specified memory location, You need to implement a function which will...

You need to implement a function which will write out a given user-specified memory location to disk in base 10. That means that you have to convert the large number data structure

Lists, In the previous unit, we have discussed arrays. Arrays are data stru...

In the previous unit, we have discussed arrays. Arrays are data structures of fixed size. Insertion and deletion involves reshuffling of array elements. Thus, array manipulation

Write down the procedure to reverse a singly linked list. , Ans: A pr...

Ans: A procedure to reverse the singly linked list: reverse(struct node **st) { struct node *p, *q, *r; p = *st; q = NULL; while(p != NULL) { r =q;

Deletion of an element from the linear array, Program will demonstrate dele...

Program will demonstrate deletion of an element from the linear array /* declaration of delete_list function */ voiddelete_list(list *, int); /* definition of delete_list

Explain about hidden-surface, Explain about Hidden-surface Hidden-line...

Explain about Hidden-surface Hidden-line removal refers to wire-frame diagrams without surface rendering and polygonal surfaces with straight edges. Hidden-surface removal ref

Illustrate the visual realism applications, Illustrate the Visual realism a...

Illustrate the Visual realism applications a)   Robot Simulations : Visualization of movement of their links and joints  and end effector movement etc. b)  CNC programs ver

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd