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

Postfix expression, : Write an algorithm to evaluate a postfix expression. ...

: Write an algorithm to evaluate a postfix expression. Execute your algorithm using the following postfix expression as your input: a b + c d +*f ­ .

Illustrate an example of algorithm, Illustrate an example of algorithm ...

Illustrate an example of algorithm Consider that an algorithm is a sequence of steps, not a program. You might use the same algorithm in different programs, or express same alg

What is class invariants assertion, What is Class invariants assertion ...

What is Class invariants assertion A class invariant is an assertion which should be true of any class instance before and after calls of its exported operations. Generally

Doubly linked list having n nodes, The time required to delete a node x fro...

The time required to delete a node x from a doubly linked list having n nodes is O (1)

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

Adjacency matrix, Q. Give the adjacency matrix for the graph drawn below:  ...

Q. Give the adjacency matrix for the graph drawn below:                                                 Ans: Adjacency matrix for the graph given to us

Define null values, Define null values.  In some cases a particular ent...

Define null values.  In some cases a particular entity might not have an applicable value for an attribute or if we do not know the value of an attribute for a particular entit

Multiple stacks in a single array, implement multiple stacks in an array an...

implement multiple stacks in an array and write different algorithms to perform operations on it

Creation of doubly linked list, Program: Creation of Doubly Linked List ...

Program: Creation of Doubly Linked List OUTPUT Input the values of the element -1111 to come out : 1 Input the values of the element -1111 to come out : 2 Inpu

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