Category: Graph

Category Archives: Graph

Algorithm: BFS(Breadth First Search)

Posted on May 26, 2017 | Leave a comment

Theory:

http://scanftree.com/Data_Structure/Breadth-First-Search

Bangla:

গ্রাফ থিওরিতে হাতেখড়ি-৪(ব্রেডথ ফার্স্ট সার্চ)

Video:

code implementation:

Some other links may help:

Breadth First Search Algorithm

code:

//bfs implementation for undirected unweighted graph
#include<fstream>
#include<queue>
#include<vector>
#include<iostream>
using namespace std;

int main()
{
    int n,m,start;
    int a,b;
    cin>>n>>m>>start;
    vector<int> samp;
    vector<vector<int> > conn(n+1,samp); //conn taking custom value in vector to make it sizeable

    //loading adjacency matrix
    for(int i=0; i<m; i++)
    {
        cin>>a>>b;
        conn[a].push_back(b);
        conn[b].push_back(a);
    }
    bool visited[n+1]; //visited node 1 to last
    for(int i=0; i<n+1; i++)
    {
        visited[i]=false;  //making each and every node false
    }
    queue<int> Q;  //creating a queue
    Q.push(start); //pushing the starting node in the queue
    visited[start]=true; //make the starting node only true
    int siz=0;
    int lev=0;
    while(!Q.empty())
    {
        cout<<"LEVEL:"<<lev<<endl;
        siz=Q.size();
        while(siz--)
        {
            int first=Q.front();
            Q.pop();
            cout<<first<<endl;
            for(int j=0; j<conn[first].size(); j++)
            {
                if(!visited[conn[first][j]])
                {
                visited[conn[first][j]]=true; //making true which have visited
                Q.push(conn[first][j]); //pushing the value in the queue
                }
            }

        }
        lev++; //level increasing in each iteration
    }
return 0;
}

//bfs implementation for undirected unweighted graph

#include<fstream>

#include<queue>

#include<vector>

#include<iostream>

using namespace std;

int main()

{

int n,m,start;

int a,b;

cin>>n>>m>>start;

vector<int> samp;

vector<vector<int> > conn(n+1,samp); //conn taking custom value in vector to make it sizeable

//loading adjacency matrix

for(int i=0; i<m; i++)

{

cin>>a>>b;

conn[a].push_back(b);

conn[b].push_back(a);

}

bool visited[n+1]; //visited node 1 to last

for(int i=0; i<n+1; i++)

{

visited[i]=false; //making each and every node false

}

queue<int> Q; //creating a queue

Q.push(start); //pushing the starting node in the queue

visited[start]=true; //make the starting node only true

int siz=0;

int lev=0;

while(!Q.empty())

{

cout<<"LEVEL:"<<lev<<endl;

siz=Q.size();

while(siz--)

{

int first=Q.front();

Q.pop();

cout<<first<<endl;

for(int j=0; j<conn[first].size(); j++)

{

if(!visited[conn[first][j]])

{

visited[conn[first][j]]=true; //making true which have visited

Q.push(conn[first][j]); //pushing the value in the queue

}

lev++; //level increasing in each iteration

}

return 0;

}

Input:

9 10 1 //here 1 is starting node that can be any value
1 2
1 3
3 4
3 5
1 6
4 6
4 9
9 8
1 7
7 3

9 10 1 //here 1 is starting node that can be any value

1 2

1 3

3 4

3 5

1 6

4 6

4 9

9 8

1 7

7 3

Output:

Another code tried to write from the pseudocode is:

#include<iostream>
#include<queue>
#include<bits/stdc++.h>
using namespace std;
//void BFS(int);
int WHITE=1,GRAY=2,BLACK=3,inf=31000,NIL=-1;
int num_e,num_v;
queue<int> Q;
int adj[20][20],color[20],d[20],p[20];
void initialization()
{
    int k,j;
    for(k=0; k<20; k++)
    {
        for(j=0; j<20; j++)
        {
            adj[k][j]=0;
        }
    }
}
void build_adj_matrix()
{
    int i,a,b;
    cin>>num_v;
    cin>>num_e;
    for(i=1; i<=num_e; i++)
    {
        cin>>a>>b;
        adj[a][b]=1;
        adj[b][a]=1;
    }
}
void BFS(int s)
{
    int i,u,v;
    for(i=1; i<=num_v; i++)
    {
        color[i]=WHITE;
        d[i]=inf;
        p[i]=NIL;
    }
    color[s]=GRAY;
    d[s]=0;
    p[s]=NIL;
    Q.push(s);
    while(!Q.empty())
    {
        int u=Q.pop();
        for(v=1; v<=num_v; v++)
        {
            if(adj[u][v]==1)
            {
                if(color[v]==WHITE)
                {
                    color[v]=GRAY;
                    d[v]=d[u]+1;
                    p[v]=u;
                    Q.push(v);
                }
            }
        }
        color[u]=BLACK;
    }
}
void distance_output()
{
    int i;
    cout<<"Shortest path from source vertex";
    for(i=1; i<=num_v; i++)
    {
        cout<<"to node "<<i<<"is "<<d[i];

    }
}
void path_print(int s,int v)
{
    if(v==s)
    {
        cout<<s<<endl;
    }
    else if(p[v]==NIL)
    {
        cout<<"No path from"<<s<<"to "<<v<<"exists";
    }
    else
    {
        path_print(s,p[v]);
        cout<<v<<endl;
    }
}
int main()
{

    int source,destination;
    initialization();
    build_adj_matrix();
    cin>>source;
    cin>>destination;
    BFS(source);
    distance_output();
    path_print(source,destination);
    return 0;
}

100

101

102

103

#include<iostream>

#include<queue>

#include<bits/stdc++.h>

using namespace std;

//void BFS(int);

int WHITE=1,GRAY=2,BLACK=3,inf=31000,NIL=-1;

int num_e,num_v;

queue<int> Q;

int adj[20][20],color[20],d[20],p[20];

void initialization()

{

int k,j;

for(k=0; k<20; k++)

{

for(j=0; j<20; j++)

{

adj[k][j]=0;

}

void build_adj_matrix()

{

int i,a,b;

cin>>num_v;

cin>>num_e;

for(i=1; i<=num_e; i++)

{

cin>>a>>b;

adj[a][b]=1;

adj[b][a]=1;

}

void BFS(int s)

{

int i,u,v;

for(i=1; i<=num_v; i++)

{

color[i]=WHITE;

d[i]=inf;

p[i]=NIL;

}

color[s]=GRAY;

d[s]=0;

p[s]=NIL;

Q.push(s);

while(!Q.empty())

{

int u=Q.pop();

for(v=1; v<=num_v; v++)

{

if(adj[u][v]==1)

{

if(color[v]==WHITE)

{

color[v]=GRAY;

d[v]=d[u]+1;

p[v]=u;

Q.push(v);

}

color[u]=BLACK;

}

void distance_output()

{

int i;

cout<<"Shortest path from source vertex";

for(i=1; i<=num_v; i++)

{

cout<<"to node "<<i<<"is "<<d[i];

}

void path_print(int s,int v)

{

if(v==s)

{

cout<<s<<endl;

}

else if(p[v]==NIL)

{

cout<<"No path from"<<s<<"to "<<v<<"exists";

}

else

{

path_print(s,p[v]);

cout<<v<<endl;

}

int main()

{

int source,destination;

initialization();

build_adj_matrix();

cin>>source;

cin>>destination;

BFS(source);

distance_output();

path_print(source,destination);

return 0;

}

reference from java code: http://www.programmingboss.com/2014/06/breadth-first-search-bfs-in-java.html

ppt slide: https://drive.google.com/file/d/0B0sCkwd_qKgJSzZyUWVYZU5GWlk/edit

Depth Firtst Search(DFS) Algorithm Explanation and Implementation in C++

Posted on December 31, 2015 | Leave a comment

Discovery Time and Finishing Time Code:

//dfs using adjacency list in directed graph
#include<iostream>
using namespace std;
int WHITE=1,GREY=2,BLACK=3,INF=310000,NIL=-1;
int num_v,num_e,time=0;
int adj[20][20],color[20],p[20],d[20],f[20];
void DFS_visit(int);
void initialization()
{
    int k,j;
    for(k=0; k<20; k++)
    {
        for(j=0; j<20; j++)
        {
            adj[k][j]=0;
        }
    }

}
void build_adj_matrix()
{
    int i,a,b;
    cout<<"Enter number of vertices: "<<endl;
    cin>>num_v;
    cout<<"Enter number of edges: "<<endl;
    cin>>num_e;
    cout<<"Enter edges: "<<endl;
    for(i=1; i<=num_e; i++)
    {
        cin>>a>>b;
        adj[a][b]=1;
    }
}
void dfs()
{
    int i,u;
    for(i=1; i<=num_v; i++)
    {
        color[i]=WHITE;
        p[i]=NIL;
    }
    for(u=1; u<=num_v; u++)
    {
        if(color[u]==WHITE)
        {
            DFS_visit(u);
        }
    }
}
void DFS_visit(int u)
{
    int i,v;
    color[u]=GREY;
    time=time+1;
    d[u]=time;
    for(v=1; v<=num_v; v++)
    {
        if(adj[u][v]==1)
        {
            if(color[v]==WHITE)
            {
                p[v]=u;
                DFS_visit(v);
            }
        }
    }
    color[u]=BLACK;
    time=time+1;
    f[u]=time;
}
void distance_output()
{
    int i;
    cout<<"Discovery time and finish time:\n";
    for(i=1; i<=num_v; i++)
    {
        cout<<"Node "<<i<<" is "<<d[i]<<"/"<<f[i]<<" \n";
    }
}
int main()
{
    initialization();
    build_adj_matrix();
    dfs();
    distance_output();
    return 0;
}

//dfs using adjacency list in directed graph

#include<iostream>

using namespace std;

int WHITE=1,GREY=2,BLACK=3,INF=310000,NIL=-1;

int num_v,num_e,time=0;

int adj[20][20],color[20],p[20],d[20],f[20];

void DFS_visit(int);

void initialization()

{

int k,j;

for(k=0; k<20; k++)

{

for(j=0; j<20; j++)

{

adj[k][j]=0;

}

void build_adj_matrix()

{

int i,a,b;

cout<<"Enter number of vertices: "<<endl;

cin>>num_v;

cout<<"Enter number of edges: "<<endl;

cin>>num_e;

cout<<"Enter edges: "<<endl;

for(i=1; i<=num_e; i++)

{

cin>>a>>b;

adj[a][b]=1;

}

void dfs()

{

int i,u;

for(i=1; i<=num_v; i++)

{

color[i]=WHITE;

p[i]=NIL;

}

for(u=1; u<=num_v; u++)

{

if(color[u]==WHITE)

{

DFS_visit(u);

}

void DFS_visit(int u)

{

int i,v;

color[u]=GREY;

time=time+1;

d[u]=time;

for(v=1; v<=num_v; v++)

{

if(adj[u][v]==1)

{

if(color[v]==WHITE)

{

p[v]=u;

DFS_visit(v);

}

color[u]=BLACK;

time=time+1;

f[u]=time;

}

void distance_output()

{

int i;

cout<<"Discovery time and finish time:\n";

for(i=1; i<=num_v; i++)

{

cout<<"Node "<<i<<" is "<<d[i]<<"/"<<f[i]<<" \n";

}

int main()

{

initialization();

build_adj_matrix();

dfs();

distance_output();

return 0;

}

input/output:

Enter number of vertices:
4
Enter number of edges:
4
Enter edges:
2 3
2 1
1 4
3 4
Discovery time and finish time:
Node 1 is 1/4
Node 2 is 5/8
Node 3 is 6/7
Node 4 is 2/3

Enter number of vertices:

Enter number of edges:

Enter edges:

2 3

2 1

1 4

3 4

Discovery time and finish time:

Node 1 is 1/4

Node 2 is 5/8

Node 3 is 6/7

Node 4 is 2/3

pseudo:

void DFS_visit(int u){
	int i,v;
	colour[u]=GREY;
	time=time+1;
	d[u]=time;
	for(v=1;v<=num_v;v++)
	{
		if(adj[u][v]==1){
			if(color[v]==WHITE){
				p[v]=u;
				DFS_visit(v);
			}
		}
	
	}
	color[u]=BLACK;
	time=time+1;
	f[u]=time;
}

void DFS_visit(int u){

int i,v;

colour[u]=GREY;

time=time+1;

d[u]=time;

for(v=1;v<=num_v;v++)

{

if(adj[u][v]==1){

if(color[v]==WHITE){

p[v]=u;

DFS_visit(v);

}

color[u]=BLACK;

time=time+1;

f[u]=time;

}

Pseudocode from shafayet vai’s blog:

procedure DFS(G, source):
  U ← source
  time  ← time+1
  d[u]  ← time
  color[u]  ← GREY
  for all edges from u to v in G.adjacentEdges(v) do        
    if color[v] = WHITE
     DFS(G,v)
    end if
  end for
  color[u] ← BLACK
  time ← time+1
  f[u] ← time
  return

procedure DFS(G, source):

U ← source

time ← time+1

d[u] ← time

color[u] ← GREY

for all edges from u to v in G.adjacentEdges(v) do

if color[v] = WHITE

DFS(G,v)

end if

end for

color[u] ← BLACK

time ← time+1

f[u] ← time

return

Reference:
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm
http://www.dotnetlovers.com/Article/182/implementation-of-depth-first-searchdfs

Another code to find the order of the node:
References:
One of my classmates blog link: http://programminghelpbd.blogspot.com/2014/06/breadth-first-search-dfs-in-java.html
and this ppt : https://drive.google.com/file/d/0B0sCkwd_qKgJZEJzS1pWeXNmNUE/edit
CLRS website: http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm

Shafayet Ashraf: http://www.shafaetsplanet.com/planetcoding/?p=973

saurabhschool youtube link : https://www.youtube.com/watch?v=gCNsAKkUHPM

Youtube video of Mifta Sintaha:

and here is also a good implementation:
http://electrofriends.com/source-codes/software-programs/cpp-programs/cpp-data-structure/c-programs-for-the-implementation-of-depth-first-searchdfs-for-a-given-graph/comment-page-1/#comments

Java array basics: http://www.tutorialspoint.com/java/java_arrays.htm

Another code to find the order of vertices:

#include<iostream>
#include<conio.h>
#include<stdlib.h>
using namespace std;
int adj[10][10],i,j,k,n,stk[10],top,v,visit[10],visited[10];

main()
{
    int m;
    cout <<"enterno of vertices";
    cin >> n;
    cout <<"ente no of edges";
    cin >> m;
    cout <<"\nEDGES \n";
    for(k=1; k<=m; k++)
    {
        cin >>i>>j;
        adj[i][j]=1;
    }

    cout <<"enter initial vertex:";
    cin >>v;
    cout <<"ORDER OF VISITED VERTICES: ";
    cout << v <<" ";
    visited[v]=1;
    k=1;
    while(k<n)
    {
        for(j=n; j>=1; j--)
            if(adj[v][j]!=0 && visited[j]!=1 && visit[j]!=1)
            {
                visit[j]=1;
                stk[top]=j;
                top++;
            }
        v=stk[--top];
        cout<<v << " ";
        k++;
        visit[v]=0;
        visited[v]=1;
    }
}

#include<iostream>

#include<conio.h>

#include<stdlib.h>

using namespace std;

int adj[10][10],i,j,k,n,stk[10],top,v,visit[10],visited[10];

main()

{

int m;

cout <<"enterno of vertices";

cin >> n;

cout <<"ente no of edges";

cin >> m;

cout <<"\nEDGES \n";

for(k=1; k<=m; k++)

{

cin >>i>>j;

adj[i][j]=1;

}

cout <<"enter initial vertex:";

cin >>v;

cout <<"ORDER OF VISITED VERTICES: ";

cout << v <<" ";

visited[v]=1;

k=1;

while(k<n)

{

for(j=n; j>=1; j--)

if(adj[v][j]!=0 && visited[j]!=1 && visit[j]!=1)

{

visit[j]=1;

stk[top]=j;

top++;

}

v=stk[--top];

cout<<v << " ";

k++;

visit[v]=0;

visited[v]=1;

}

Category Archives: Graph

Algorithm: BFS(Breadth First Search)

Depth Firtst Search(DFS) Algorithm Explanation and Implementation in C++

Caution and Tips:

About Me & MyBlog

Category

Recent Posts

Recent Comments

My Facebook

Follow Me

My Algorithmic Progress in OJ’s

My Github

My Linkedin

Count per Day

Archives

This site is powered by:

Bookmarks

My Coding Page

Category Archives: Graph

Algorithm: BFS(Breadth First Search)

Depth Firtst Search(DFS) Algorithm Explanation and Implementation in C++

Caution and Tips:

About Me & MyBlog

Category

Recent Posts

Recent Comments

My Facebook

Follow Me

My Algorithmic Progress in OJ’s

My Github

My Linkedin

Tags

Count per Day

Archives

This site is powered by:

Bookmarks

My Coding Page