true

Take BTech Tuition from the Best Tutors

• Affordable fees
• 1-1 or Group class
• Flexible Timings
• Verified Tutors

Search in

# Depth First Traversal For A Graph

D Subba Rao
05/02/2018 0 0

Depth First Traversal (or Search) for a graph is similar to Depth First Traversal of a tree. The only catch here is, unlike trees, graphs may contain cycles, so we may come to the same node again. To avoid processing a node more than once, we use a boolean visited array.

For example, in the following graph, we start traversal from vertex 2. When we come to vertex 0, we look for all adjacent vertices of it. 2 is also an adjacent vertex of 0. If we don’t mark visited vertices, then 2 will be processed again and it will become a non-terminating process. A Depth First Traversal of the following graph is 2, 0, 1, 3.

Following are implementations of simple Depth First Traversal. The C++ implementation uses adjacency list representation of graphs. STL‘s list container is used to store lists of adjacent nodes.

First Traversal (or Search) for a graph is similar to Depth First Traversal of a tree. The only catch here is, unlike trees, graphs may contain cycles, so we may come to the same node again. To avoid processing a node more than once, we use a boolean visited array.

For example, in the following graph, we start traversal from vertex 2. When we come to vertex 0, we look for all adjacent vertices of it. 2 is also an adjacent vertex of 0. If we don’t mark visited vertices, then 2 will be processed again and it will become a non-terminating process. A Depth First Traversal of the following graph is 2, 0, 1, 3.

Following are implementations of simple Depth First Traversal. The C++ implementation uses adjacency list representation of graphs. STL‘s list container is used to store lists of adjacent nodes.

`// C++ program to print DFS traversal from`
`// a given vertex in a  given graph`
`#include`
`#include`
`using` `namespace` `std;`

`// Graph class represents a directed graph`
`// using adjacency list representation`
`class` `Graph`
`{`
`    ``int` `V;    ``// No. of vertices`

`    ``// Pointer to an array containing`
`    ``// adjacency lists`
`    ``list<``int``> *adj;`

`    ``// A recursive function used by DFS`
`    ``void` `DFSUtil(``int` `v, ``bool` `visited[]);`
`public``:`
`    ``Graph(``int` `V);   ``// Constructor`

`    ``// function to add an edge to graph`
`    ``void` `addEdge(``int` `v, ``int` `w);`

`    ``// DFS traversal of the vertices`
`    ``// reachable from v`
`    ``void` `DFS(``int` `v);`
`};`

`Graph::Graph(``int` `V)`
`{`
`    ``this``->V = V;`
`    ``adj = ``new` `list<``int``>[V];`
`}`

`void` `Graph::addEdge(``int` `v, ``int` `w)`
`{`
`    ``adj[v].push_back(w); ``// Add w to v’s list.`
`}`

`void` `Graph::DFSUtil(``int` `v, ``bool` `visited[])`
`{`
`    ``// Mark the current node as visited and`
`    ``// print it`
`    ``visited[v] = ``true``;`
`    ``cout << v << ``" "``;`

`    ``// Recur for all the vertices adjacent`
`    ``// to this vertex`
`    ``list<``int``>::iterator i;`
`    ``for` `(i = adj[v].begin(); i != adj[v].end(); ++i)`
`        ``if` `(!visited[*i])`
`            ``DFSUtil(*i, visited);`
`}`

`// DFS traversal of the vertices reachable from v.`
`// It uses recursive DFSUtil()`
`void` `Graph::DFS(``int` `v)`
`{`
`    ``// Mark all the vertices as not visited`
`    ``bool` `*visited = ``new` `bool``[V];`
`    ``for` `(``int` `i = 0; i < V; i++)`
`        ``visited[i] = ``false``;`

`    ``// Call the recursive helper function`
`    ``// to print DFS traversal`
`    ``DFSUtil(v, visited);`
`}`

`int` `main()`
`{`
`    ``// Create a graph given in the above diagram`
`    ``Graph g(4);`
`    ``g.addEdge(0, 1);`
`    ``g.addEdge(0, 2);`
`    ``g.addEdge(1, 2);`
`    ``g.addEdge(2, 0);`
`    ``g.addEdge(2, 3);`
`    ``g.addEdge(3, 3);`

`    ``cout << ``"Following is Depth First Traversal"`
`            ``" (starting from vertex 2) \n"``;`
`    ``g.DFS(2);`

`    ``return` `0;`
`}`
0 Dislike

## Other Lessons for You

Do You Give Enough Importance In Writing Main () In C Language?
I am sure; you guys are quite familiar with C programming, especially, while it comes to write the first line of your main function. In my class, I have seen many of my students are writing main function...

Computer Awareness: Important Abbreviations
Important Abbreviations:1. ANSI: American National Standards Institute. 2. ASCII: American Standard Code for Information Interchange. 3. CGA: Colour Graphics Adapter. 4. DOS: Disk Operating System. 5....
P

Parul S.

Getting A Bit Deeper Into Time Complexity Analysis
What is Time Complexity Analysis? In the last blog, you got a rough idea about the Time Complexity and that was all about to judge how fast the algorithm can run, or putting it in another way, how much...

Pointers And References
Are reference and pointers same? No. I have seen this confusion crumbling up among the student from the first day. So better clear out this confusion at thevery beginning. Pointers and reference both...

Machine Learning Introduction
This is the age of “big data.” Once upon a time, only companies had raw data. There used to be servers where that data was stored and processed. First with the arrival of personal computers...

### Looking for BTech Tuition ?

Learn from Best Tutors on UrbanPro.

Are you a Tutor or Training Institute?

Join UrbanPro Today to find students near you
X

### Looking for BTech Tuition Classes?

The best tutors for BTech Tuition Classes are on UrbanPro

• Select the best Tutor
• Book & Attend a Free Demo
• Pay and start Learning

### Take BTech Tuition with the Best Tutors

The best Tutors for BTech Tuition Classes are on UrbanPro