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 回答 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);
            }
    }
于 2013-09-19T14:59:24.747 回答
2

您得到的输出对于无向图是正确的。您提供的边列表包括 (6,8)，但 DFS 可以从 8 到 6 以及从 6 到 8 行进，因为它是无向的。如果您想要一个有向图，则必须对a数组的设置方式进行一些更改。

于 2013-09-19T14:50:02.993 回答
0

输出是正确的。在您的示例中，当 dfs() 中的 i = 4 时递归停止（在顶点 5 中停止），并且它回到顶点 8，它来自哪里（i = 7）。在这个调用中，我们刚刚从 j = 4（没有更多相邻顶点的那个）返回。循环索引递增 (j++)，并且因为顶点 8 连接到顶点 6​​ (j = 5)，所以下一次递归调用将有 i = 5，所以您正在访问顶点 6。从顶点 6 开始，递归到 3然后是 7，然后一切都恢复了。

于 2013-09-19T15:04:02.473 回答
0

你可以试试这个 DFS 的实现：

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 。我希望它有所帮助。

于 2016-08-07T00:19:58.637 回答