Implementing DFS in Java

import java.io.*;
import java.util.*;
class anbfs
{
	public static void main(String args[])throws IOException
	{
		dfs d = new dfs();
	}
}

class dfs
{
	public int m[][]=new int[50][50];
	public int n,i,j,k,l;
	
	public int q[] = new int[100];
	public int qpos;
	
	public dfs() throws IOException
	{
		//Input
		System.out.println("Enter n:");
		BufferedReader obj = new BufferedReader(new InputStreamReader(System.in));
		n= Integer.parseInt(obj.readLine());
		
		l=0;
		System.out.println("Enter matrix:");
		for(i=0;i<n;i++)
		{
			for(j=0;j<n;j++)
			{
				m[i][j] = Integer.parseInt(obj.readLine());
			}
		}
		
		//Printing entered values
		System.out.println("Entered matrix is:");
		for(i=0;i<n;i++)
		{
			for(j=0;j<n;j++)
			{
				System.out.print(m[i][j]+" ");
			}
			System.out.println();
		}
		
		//inserting first element
		q[0]=1;
		qpos = 1;
		i=0;
		
		//Recursively call the function with first element
		finddfs(q[i]-1);
		
		System.out.println("DFS Output:");
		for(j=0;j<qpos;j++)
		{
			System.out.print(q[j]+" ");
		}
	}
	
	public void finddfs(int a)
	{
		int j, c = a;
		for(j=c;j<n;j++)
		{
			if (m[j]!=0)
			{
				for(k=0;k<qpos;k++)
				{
					l=0; //flag
					if (q[k]==j+1)
					{
						l=1;
					}
				}
				if (l==0)
				{
					q[qpos]=j+1;
					qpos = qpos+1 ;
					finddfs(j);
				}
			}
		}
	}
}

/* OUTPUT
Enter n:
8
Enter matrix:
0
1
1
1
0
0
0
0
1
0
0
0
1
1
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
Entered matrix is:
0 1 1 1 0 0 0 0 
1 0 0 0 1 1 0 0 
1 0 0 0 0 0 0 0 
1 0 0 0 0 0 1 1 
0 1 0 0 0 0 0 0 
0 1 0 0 0 0 0 0 
0 0 0 1 0 0 0 0 
0 0 0 1 0 0 0 0 
DFS Output:
1 2 5 6 3 4 7 8 
*/

Leave a Reply

Your email address will not be published. Required fields are marked *