Depth First Search

//WAP to implement Depth First Search

#include<stdio.h>
#include<conio.h>

int n,adj[10][10],visited[10];
void input();
void dfs(int);

int main()
{
	int s;
	printf("Enter no. of nodes in a Graph ");
	scanf("%d",&n);
	input();
	printf("From which node u wanna start dfs ");
	scanf("%d",&s);
	if(s>n)
		printf("Invalid node ");
	else
	{
		printf("DFS output is :\n");
		dfs(s);
	}
	return 0;
}

void input()
{
	int i,j,nbr;
	char ch;
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
		adj[i][j]=0;	//initialise adjacency matrix to 0
	for(i=1;i<=n;i++)
	{
		printf("\nWant to add neighbour(s) of %d (y/n) ",i);
		fflush(stdin);
		scanf("%c",&ch);
		while(ch=='y')	//input neighbour of each vertex
		{
			printf("Enter neighbour ");
			scanf("%d",&nbr);
			if(nbr>n)
			{
			printf("Invalid neighbour");
			break;
			}
			adj[i][nbr]=1;
			adj[nbr][i]=1;
			printf("Wanna add more neighbour(y/n): ");
			fflush(stdin);
			scanf("%c",&ch);
		}
	}
	printf("adj mat. is :\n");	//print the adjacency matrix
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			printf("%d\t",adj[i][j]);
		}
		printf("\n");
	}
}

void dfs(int s)
{
	int stack[10],top=-1,out,i;
	for(i=1;i<=n;i++)
	{
		visited[i]=0;	//initialise every vertex to be non visited
	}
	visited[s]=1;		//initialise starting vertex to be visited
	top++;
	stack[top]=s;
	while(top!=-1)
	{
		out=stack[top];	//make node out of stack
		top--;
		printf("%d ",out);
		visited[out]=1;   //make node visited
		for(i=1;i<=n;i++)
		{  //put adjacent nodes of out node in stack
			if(adj[out][i]==1&&visited[i]!=1)
			{
				top++;
				stack[top]=i;
			}
		}
	}
}

import java.io.*;
class dfs
{
static void dfs(int a[][], int m[], int i, int n)
{
	int j;
	System.out.println("\t" + (i+1));
	m[i] = 1;
	for(j=0; j<n; j++)
		if(a[i][j]==1 && m[j]==0)
			dfs(a,m,j,n);
}

public static void main(String args[]) throws IOException
{
	int  n, i, j;
	System.out.println("No. of vertices : ");
	           BufferedReader br= new BufferedReader (new InputStreamReader(System.in));
	n =Integer.parseInt(br.readLine());
	int m[]= new int[n];
	int a[][] = new int[n][n];
	for (i=0; i<n; i++)
	{
		m[i] = 0;
	}
	System.out.println("\n\nEnter 1 if edge is present, 0 if not");
	for (i=0; i<n; i++)
	{
		System.out.println("\n");
		for (j=i; j<n; j++)
		{
			System.out.println("Edge between " + (i+1) + " and " +	(j+1)+ " : ");
			a[i][j] =Integer.parseInt(br.readLine());
			a[j][i]=a[i][j];
		}
		a[i][i] = 0;
	}
	System.out.println("\nOrder of accessed nodes : \n");
	for (i=0; i<n; i++)
		if (m[i]==0)
			dfs(a,m,i,n);

	
}
}