java mise en œuvre de parcours en Profondeur d'Abord de Recherche

le code suivant ne comporte pas d'erreurs,mais le résultat que j'obtiens n'est pas 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);
}
}

Exemple De Sortie

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 chemin d'accès doit être : 1 2 4 8 5 3 6 7

la sortie que je reçois est : 1 2 4 8 5 6 3 7

avis que la 6 ème et 7 ème termes sont interchangeables

quelqu'un peut me dire comment remédier à cela.merci pour votre aide

InformationsquelleAutor jake | 2013-09-19
  1. 2

    La sortie que vous obtenez est correct pour un graphe non-dirigé. La liste des bords que vous avez fourni comprend (6,8), mais d'un DFS peut se déplacer de 8 à 6 ainsi que de 6 à 8, car il est non-orienté. Si vous souhaitez un graphe orienté, vous aurez à faire quelques changements dans la façon dont les a tableau est mis en place.

    InformationsquelleAutor ajb
  2. 4

    - je changer la mise en œuvre de votre dfs, maintenant il shopuld fonctionne, si vous utilisez des noms de variables, afin de les rendre plus reconnaissable, vous pouvez obtenir votre aide rapide

    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

    La sortie est correcte. Avec votre exemple, la récursion s'arrête lorsque i = 4 dfs() (s'arrête au sommet 5), et il serpente le dos de vertex 8, d'où il vient (avec i = 7). Dans cet appel, nous venons de rentrer de j = 4 (celui qui n'avaient pas plus de sommets adjacents). L'indice de boucle est incrémenté (j++), et parce que les vertex 8 est connecté au sommet 6 (j = 5), le prochain appel récursif aura i = 5, de sorte que vous êtes en visite vertex 6. À partir du sommet 6, la récursivité passe à 3, puis 7, puis les vents tout en arrière.

    InformationsquelleAutor Filipe Gonçalves
  4. 0

    Vous pouvez essayer cette mise en œuvre de 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);
}
}
}

    C'est récursive de mise en œuvre. Pour plus d'informations, veuillez visiter: https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/TreeTraverse.java. J'espère que cela aide.

    InformationsquelleAutor Vahid