Like us on google+

Wednesday, 21 May 2014

Widgets

Depth First Search(DFS)

#include<stdio.h>
int n;
void dfs(int visit[n],int src,int a[n][n]);


int main()
{

int i,j,source;

printf("enter the value of n\n");
scanf("%d",&n);
int a[n][n];
int visit[n];

printf("enter the adjacency matrix\n");
for (i = 0; i <n; ++i)
{
for (j = 0;j<n; ++j)
{
scanf("%d",&a[i][j]);
visit[i]=0;

}
}
printf("enter the source");
scanf("%d",&source);
visit[source]=1;

dfs(visit,source,a);
}

void dfs(int v[n],int src,int a[n][n])
{
int i;
v[src]=1; // mark source as visited
for(i=0;i<n;i++)
{
if(!v[i] && a[src][i]) //if v[i] is not marked and a[src][i]=1 then proceed
{
printf("%d--%d\n",src,i); //print the path
dfs(v,i,a); // calling recursively
}
}
}
----------------------------------------------------------------------------------------------------------------------
OUTPUT:
enter the value of n
4
enter the adjacency matrix
0 1 1 1
1 0 1 0
1 1 0 0
1 0 0 0
enter the source 0
0--1
1--2
0--3

SHARE THIS POST   

  • Facebook
  • Twitter
  • Myspace
  • Google Buzz
  • Reddit
  • Stumnleupon
  • Delicious
  • Digg
  • Technorati
About us:
Hi guys Sandesh and Rajesh here ... studing engineering in PESIT started this blog as a google contest and also we love blogging ...Hope u like it ...Encourage us by liking us on g+... Any queries dont hesitate to ask Read More →

0 comments: