Java实现深度优先搜索算法

3
以下代码没有错误,但是我得到的输出结果不正确。
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。

我得到的输出是:1 2 4 8 5 6 3 7。

请注意,第6个和第7个术语被交换了。

有人能告诉我如何纠正这个问题。谢谢你的帮助。

4个回答

4

我改变了你的dfs实现,现在它应该可以正常工作。如果你使用变量名来使它们更加易识别,你就可以更快地得到帮助。

static void dfs(int adjacencyMatrix[][], int vertex, int[] visited) {

        System.out.println("visiting " + (vertex + 1) );


        for (int j = vertex + 1; j < adjacencyMatrix[vertex].length; j++)
            if (adjacencyMatrix[vertex][j] == 1 && visited[j] == 0) {
                visited[j] = 1;
                dfs(adjacencyMatrix, j, visited);
            }
    }

2
你得到的输出对于无向图是正确的。你提供的边列表包括(6,8),但是由于是无向图,DFS可以从8到6,就像从6到8一样。如果你想要一个有向图,你需要在设置a数组的方式上做出一些改变。

0
你可以尝试这个深度优先搜索的实现:
import java.util.ArrayList;
import java.util.List;

public class TreeTraverse {

    static class Node{
        Node(int data){
            this.data = data;
            this.left = null;
            this.right = null;
            this.visited = false;
        }
        int data;
        Node left;
        Node right;
        boolean visited;
    }

    public static void main(String[] args) {
        //The tree:
        //   1
        //  / \
        // 7   9
        // \  / \
        //  8 2 3

        Node node1 = new Node(1);
        Node node7 = new Node(7);
        Node node9 = new Node(9);
        Node node8 = new Node(8);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        node1.left = node7;
        node1.right = node9;
        node7.right = node8;
        node9.right = node3;
        node9.left = node2;
        System.out.println("DFS: ");
        depthFirstSearch(node1);

    }

    private static void depthFirstSearch(Node node){
        if(node.left == null && node.right == null){
            System.out.print(node.data+" ");
            node.visited = true;
        }else if(node.left == null || node.left.visited){
            depthFirstSearch(node.right);
            System.out.print(node.data+" ");
            node.visited = true;
        }else{
            depthFirstSearch(node.left);
            node.visited = true;
            System.out.print(node.data+" ");
            depthFirstSearch(node.right);

        }
    }

}

这是它的递归实现。更多信息请访问:https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/TreeTraverse.java。希望能对您有所帮助。

0
输出是正确的。在您的示例中,递归在dfs()中i = 4时停止(在顶点5停止),然后回到它来自的顶点8(i = 7)。在此调用中,我们刚从j = 4返回(没有更多相邻顶点的那个)。循环索引递增(j ++),因为顶点8连接到顶点6(j = 5),所以下一个递归调用将具有i = 5,因此您正在访问顶点6。从顶点6开始,递归进入3,然后进入7,然后一切都回来了。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接