Skip to content

Instantly share code, notes, and snippets.

@rushike
Created August 6, 2017 14:05
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save rushike/2d3521cc6dc545e4f06183896f2f806a to your computer and use it in GitHub Desktop.
Save rushike/2d3521cc6dc545e4f06183896f2f806a to your computer and use it in GitHub Desktop.
Graph-DFS-Adjcent Matrix
#include<stdio.h>
int a[10][10],b2[10][10],s[10],v[10],w[10];
int n,b=-1,r,st=0;
void print(int n);
void getMat(int n);
int push(int n);
int pop();
void traverse();
void initial(int n);
void main()
{
int i;
printf("Enter no. node you want");
scanf("%d",&n);
initial(n);
getMat(n);
print(n);
printf("Enter point to stop");
scanf("%d",&r);
r--;
traverse(n);
}
//intialize 2D Matrix
void initial(int n)
{
int i,j;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
a[i][j]=0;
}
printf("\n\n");
}
}
//Get matrix
void getMat(int n)
{
int g,i,j,k;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
printf("To node %d to the node %d\n Enter '1' or else '0'",i+1,j+1);
scanf("%d",&g);
if(g!=0)
{
a[i][j]=1;
}
}
printf("\n\n");
}
}
//Printing Matrix
void print(int n)
{
int i,j,k;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
printf("%d " ,a[i][j]);
}
printf("\n\n");
}
}
//Stack
int push(int n)
{
s[st]=n;
st++;
b++;
;
return st;
}
int pop()
{
st--;
b--;
return st;
}
//Traverse
void traverse(int n)
{
int i=0,j=0,k=0,l=0;
push(0);
while(l<n+1)
{
pop();
printf("\n\nb=%d \n",b);
k=s[b+1];
v[k]=1;
if(v[r]==1)
{
printf("There exist root form 0 to %d ",r+1);
break;
}
else
{
printf("Can't go from 0 to %d",r+1);
}
j=0;
while(j<n+1&&v[k]==1)
{
if(a[i][j]==1&&v[j]!=1)
{
push(j);
}
j++;
}
printf("k=%d\t",k);
l++;
}
printf("\n\n");
for(i=0;i<10;i++)
{
printf("%d ",s[i]);
}
printf("\n\n");
for(i=0;i<10;i++)
{
printf("%d ",v[i]);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment