Depth-first search Implementation

1 thing i always remember about dfs is "Using dfs We go to the depth of a node and then we come back"

I learned dfs from my friend and from this blog shafaetsplanet . In shafaetsplanet the algorithm is explained very easily.


Algorithm :

	DFS(G)
	1.for each vertex u ∈ G.V
	2. u.visited = false
	3. u.parent = null
	4.for each vertex u ∈ G.V
	5. if u.visited == false
	6. DFS_VISIT(u)
	DFS_VISIT(G,u)
	1.u.visited = true;
	2.for each vertex v ∈ G.Adj[u]
	3. if v.visited == false
	4. v.parent = u
	5. DFS_VISIT(G,v)

view raw dfs.txt hosted with ❤ by GitHub

Basic DFS Traversal of a Graph:


Here starting node is 0.

	#include<bits/stdc++.h>
	using namespace std;
	vector<int>v[100];
	bool visited[100];
	int parent[100];
	int n,e;
	int cyc;
	void dfs_visit(int x){
	visited[x]=true;
	for(int i=0;i<v[x].size();i++){
	int xx = v[x][i];
	if(visited[xx]==false) {
	parent[xx]=x;
	dfs_visit(xx);
	}
	}
	}
	void dfs(){
	for(int i=1;i<=n;i++){
	visited[i]=false;
	parent[i]=NULL;
	}
	for(int i=1;i<=n;i++){
	if(visited[i]==false){
	dfs_visit(i);
	}
	}
	}
	int main(){
	cin>>n>>e;
	for(int i=0;i<e;i++){
	int a,b;
	cin>>a>>b;
	v[a].push_back(b);
	}
	cyc=0;
	dfs();
	if(cyc==1) cout<<"cycle detected\n";
	cout<<"NODE: ";
	for(int i=1;i<=n;i++){
	cout<<i<<" ";
	}
	cout<<"\nPARE: ";
	for(int i=1;i<=n;i++){
	cout<<parent[i]<<" ";
	}
	}
	/*
	7 7
	1 2
	2 1
	1 3
	2 3
	3 4
	4 5
	6 7
	*/

view raw dfs.cpp hosted with ❤ by GitHub