jake - 1 year ago 104

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

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

Answer Source

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.

Recommended from our users: **Dynamic Network Monitoring from WhatsUp Gold from IPSwitch**. ** Free Download**