-
Notifications
You must be signed in to change notification settings - Fork 9
/
Copy pathDFS_traversal
62 lines (57 loc) · 1.39 KB
/
DFS_traversal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
//Program to traverse a Tree or Graph using DFS :
//Code:
#include <iostream>
#include <list>
using namespace std;
//graph class for DFS traversal
class DFSGraph
{
int V; // No. of vertices
list<int> *adjList; // adjacency list
void DFS_util(int v, bool visited[]); // A function used by DFS
public:
// class Constructor
DFSGraph(int V) {
this->V = V;
adjList = new list<int>[V];
}
// function to add an edge to graph
void addEdge(int v, int w){
adjList[v].push_back(w); // Add w to v’s list.
}
void DFS(); // DFS traversal function
};
void DFSGraph::DFS_util(int v, bool visited[]){
// current node v is visited
visited[v] = true;
cout << v << " ";
// recursively process all the adjacent vertices of the node
list<int>::iterator i;
for(i = adjList[v].begin(); i != adjList[v].end(); ++i)
if(!visited[*i]) DFS_util(*i, visited);
}
// DFS traversal
void DFSGraph::DFS(){
// initially none of the vertices are visited
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
// explore the vertices one by one by recursively calling DFS_util
for (int i = 0; i < V; i++)
if (visited[i] == false)
DFS_util(i, visited);
}
int main(){
// Create a graph
DFSGraph gdfs(5);
gdfs.addEdge(0, 1);
gdfs.addEdge(0, 2);
gdfs.addEdge(0, 3);
gdfs.addEdge(1, 2);
gdfs.addEdge(2, 4);
gdfs.addEdge(3, 3);
gdfs.addEdge(4, 4);
cout << "Depth-first traversal for the given graph:"<<endl;
gdfs.DFS();
return 0;
}