java实现深度优先搜索 [英] java implementation of Depth First Search

问题描述

以下code没有错误，但我得到的输出是不正确的。

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

DFS路径应该是：1 2 4 8 5 3 6 7

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

我得到的输出为：1 2 4 8 5 6 3 7

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

公告称，6日和7日的术语互换

notice that the 6 th and 7 th terms are interchanged

谁能告诉我如何纠正this.thanks对您有所帮助。

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

推荐答案

你得到的输出是一个无向图是正确的。你提供边缘的列表包括（6,8），但是一个DFS可以从8到6只以及6至8行进，因为它是无向。如果你想有向图，你将不得不作出在 A 数组如何设置一对夫妇的变化。

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.

这篇关于java实现深度优先搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！