java-Implementierung von Depth-First-Suche

der folgende code hat keine Fehler,aber die Ausgabe die ich erhalte ist nicht korrekt

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


}
}

Ausgabe Beispiel

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

den DFS-Pfad sollte sein : 1 2 4 8 5 3 6 7

den Ausgang bin ich immer : 1 2 4 8 5 6 3 7

beachten Sie, dass der 6 TEN und 7 TEN Bedingungen sind vertauscht

kann mir jemand sagen, wie das zu korrigieren.vielen Dank für Ihre Hilfe

InformationsquelleAutor jake | 2013-09-19

  1. 2

    Die Ausgabe, die Sie bekommen, ist die richtige für ein ungerichteter graph. Die Liste der Kanten, die Sie zur Verfügung gestellt gehören (6,8), aber ein DFS-Reisen können von 8 auf 6 genauso gut wie von 6 auf 8, da es ungerichtete. Wenn Sie möchten, dass ein gerichteter graph, dann müssen Sie ein paar Veränderungen, wie die a array eingerichtet ist.

    InformationsquelleAutor ajb

  2. 4

    ich ändern Implementierung der dfs, jetzt ist es shopuld funktioniert, wenn Sie die Namen der Variablen, damit Sie besser erkennbar sind, können Sie Ihr helfen, schneller

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

    InformationsquelleAutor user902383

  3. 0

    Die Ausgabe korrekt ist. Mit deinem Beispiel, die Rekursion Stoppt, wenn i = 4 in (dfs) (hält in vertex 5), und es windet wieder vertex 8, wo es herkam (mit i = 7). In diesem Aufruf, wir sind gerade zurück aus j = 4 (der, der hatte keine mehr benachbarten Knoten). Der loop-index wird inkrementiert (j++), und da die vertex 8 angeschlossen ist, zu Eckpunkt 6 (j = 5), der nächste rekursive Aufruf wird mit i = 5, so Sie zu Besuch sind vertex-6. Von vertex-6, die Rekursion geht bis 3 und dann 7 und dann alles windet zurück.

    InformationsquelleAutor Filipe Gonçalves

  4. 0

    Können Sie versuchen, diese Implementierung von 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);

        }
    }

}

    Dies ist eine rekursive Implementierung. Für weitere Informationen besuchen Sie bitte: https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/TreeTraverse.java. Ich hoffe, es hilft.

    InformationsquelleAutor Vahid

Schreibe einen Kommentar