DFS implementation using stack
#include<stdio.h>
int arr[10][10],visited[10],n;
void dfs(int);
int main(){
int i,j;
printf("Enter no of vertices :\n");
scanf("%d",&n);
printf("Enter adjacency matrix \n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&arr[i][j]);
for(i=0;i<n;i++)
visited[i]=0;
dfs(0);
}
void dfs(int start){
int stack[n],top=-1,i;
top++;
stack[top]=start;
visited[start]=1;
while(top>=0){
start=stack[top];
for(i=0;i<n;i++){
if((arr[start][i]==1)&&(visited[i]==0)){
stack[++top]=i;
visited[i]=1;
printf("%c\n",start+65);
break;
}
}
if(top==n)
top--;
}
}
int arr[10][10],visited[10],n;
void dfs(int);
int main(){
int i,j;
printf("Enter no of vertices :\n");
scanf("%d",&n);
printf("Enter adjacency matrix \n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&arr[i][j]);
for(i=0;i<n;i++)
visited[i]=0;
dfs(0);
}
void dfs(int start){
int stack[n],top=-1,i;
top++;
stack[top]=start;
visited[start]=1;
while(top>=0){
start=stack[top];
for(i=0;i<n;i++){
if((arr[start][i]==1)&&(visited[i]==0)){
stack[++top]=i;
visited[i]=1;
printf("%c\n",start+65);
break;
}
}
if(top==n)
top--;
}
}
Comments
Post a Comment