jake - 6 months ago 49

Java Question

the following code has no errors,but the output i am getting is not correct

`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);

}

}

`No of vertices : 8`

edges

1 2

1 3

2 4

2 5

3 6

3 7

4 8

5 8

6 8

7 8

the DFS path should be : 1 2 4 8 5 3 6 7

the output i am getting is : 1 2 4 8 5 6 3 7

notice that the 6 th and 7 th terms are interchanged

can anyone tell me how to correct this.thanks for your help

Answer

The output you're getting is correct for an undirected graph. The list of edges you provided includes (6,8), but a DFS can travel from 8 to 6 just as well as from 6 to 8 since it's undirected. If you want a directed graph, you'll have to make a couple changes in how the `a`

array is set up.