Algorithms/dfs.cpp at master · ankit-singh-dungriyal/Algorithms · GitHub

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
63
64
65
66
67
68
69
70
71
72
73
//Depth First Search (DFS) for the following graph
/* (0)-----(1)
    |     / |  \
	|   /   |  (2)
    | /     |  /
   (4)-----(3)
*/

#include<bits/stdc++.h>
using namespace std;

//creating adjacency list
void add(vector<int>adj[],int u, int v)
{
	adj[u].push_back(v);
	adj[v].push_back(u);
}

void print(vector<int>adj[],int n)
{

	cout<<"graph ( Adjacency list ):\n";
	for(int i=0;i<n;i++)
	{
		for(auto x:adj[i])
		{
			cout<<x<<"->";
		}
		cout<<endl;
	}
}

//function to do dfs for the graph
void dfs_ut(vector<int>adj[],int i, vector<bool>&visited)
{
	visited[i]=true;
	cout<<i<<", ";
	for(int j=0;j<adj[i].size();j++)
	{
		if(visited[adj[i][j]]==false)
		dfs_ut(adj,adj[i][j],visited);
	}
}

//function that call dfs_ut() for all unvisited verticies.
void dfs(vector<int>adj[],int n)
{
	cout<<"Depth Search Traversal starting from node '0':\n";
	vector<bool>visited(n);
	for(int i=0;i<n;i++)
	visited[i]=false;
	for(int i=0;i<n;i++)
	{
		if(visited[i]==false)
		dfs_ut(adj,i,visited);
	}
}

main()
{
int n=5;
vector<int>adj[n];
add(adj,0,1);
add(adj,0,4);
add(adj,1,2);
add(adj,1,3);
add(adj,1,4);
add(adj,2,3);
add(adj,3,4);
print(adj,n);
cout<<endl;
dfs(adj,n);
}