La profondeur de la Première Traversée et Adj Matrice

Je suis en train de faire un parcours en profondeur d'abord la traversée. Je n'ai aucune idée si je suis de près. Maintenant, c'est de l'impression 1 3 4 5. Il convient de l'impression 1 2 4 7 3 5 6. L'aide ou des conseils est apprécié. Merci. 🙂

Classe:

 public class myGraphs {
Stack<Integer> st;
int vFirst;
int[][] adjMatrix;
int[] isVisited = new int[7];
public myGraphs(int[][] Matrix) {
this.adjMatrix = Matrix;
st = new Stack<Integer>();
int i;
int[] node = {1, 2, 3, 4, 5, 6, 7};
int firstNode = node[0];
for (i = 1; i < node.length - 1; i++) {
depthFirst(firstNode, node[i]);
}
}
public void depthFirst(int vFirst, int n) {
int v, i;
st.push(vFirst);
while (!st.isEmpty()) {
v = st.pop();
if (isVisited[v]==0) {
System.out.print("\n"+v);
isVisited[v]=1;
}
for ( i=1;i<=n;i++) {
if ((adjMatrix[v][i] == 1) && (isVisited[i] == 0)) {
st.push(v);
isVisited[i]=1;
System.out.print(" " + i);
v = i;
}
}
}
}
//
public static void main(String[] args) {     
//1  2  3  4  5  6  7
int[][] adjMatrix = { {0, 1, 1, 0, 0, 0, 0},
{1, 0, 0, 1, 1, 1, 0},
{1, 0, 0, 0, 0, 0, 1},
{0, 1, 0, 0, 0, 0, 1},
{0, 1, 0, 0, 0, 0, 1},
{0, 1, 0, 0, 0, 0 ,0},
{0, 0, 1, 1, 1, 0, 0}  };
new myGraphs(adjMatrix);
}
}

Profondeur d'abord la recherche de quoi?
Sa profondeur de recherche pour un graphique.
Mais ce que vous cherchez?
Tu vas avoir à définir la "profondeur" ici. Par ma lecture, je m'attends à [1 2 4 7 3 5 6], depuis le 7 peut aller à 3 et 5.
L'OP-à-dire de la profondeur d'abord traversée.
la recherche de la traversée
Je pense que votre
Je pense que tout le bas de la enfants devrait venir en premier hein?
n'est pas le terme correct ici.
de toute façon, je suis le seul à en arriver à 4 chiffres à l'affichage, j'ai besoin de 7
avez-vous essayé de marcher à travers votre code dans un débogueur pour découvrir pourquoi son comportement s'écarte de ce que vous attendez?

InformationsquelleAutor TMan | 2011-11-11

graph java

4

Si vous êtes à la recherche en Profondeur d'Abord la Traversée de ce qui suit est le code de changements que vous devez faire

1) d'Abord déclarer votre nœud de tableau comme int[] node = {0, 1, 2, 3, 4, 5, 6}. Cela devrait être fait pour éviter d'index de tableau de démarrage (qui est 0 ) et votre nœud de numéro de départ (qui est 1). DONC, ici, maintenant, nous supposons que les nouveaux noms de votre nœud 1 est 0, le nœud 2 est 1......et le nœud 7 est 6.

2) au Lieu de faire
```
for (i = 1; i < node.length-1; i++){
depthFirst(firstNode, node[i]);
} 
```
dans myGraphs faire :
depthFirst(firstNode, 7);

3)Dans depthFirst au lieu de for ( i=1;i<=n;i++) utilisation for ( i=0;i<n;i++) Tout en faisant Système.out.println en fonction depthFirst ajouter un à le numéro de 0 représente le nœud 1, 1 représente le nœud 2 et ainsi de suite.

Ci-dessous est pleinement fonctionnel code que j'ai modifié :
```
import java.util.Stack;
public class DFS {
Stack<Integer> st;
int vFirst;
int[][] adjMatrix;
int[] isVisited = new int[7];
/**
* @param args
*/
public static void main(String[] args) {
int[][] adjMatrix = { {0, 1, 1, 0, 0, 0, 0},
{1, 0, 0, 1, 1, 1, 0},
{1, 0, 0, 0, 0, 0, 1},
{0, 1, 0, 0, 0, 0, 1},
{0, 1, 0, 0, 0, 0, 1},
{0, 1, 0, 0, 0, 0 ,0},
{0, 0, 1, 1, 1, 0, 0}  };
new DFS(adjMatrix);
}
public DFS(int[][] Matrix) {
this.adjMatrix = Matrix;
st = new Stack<Integer>();
int i;
int[] node = {0, 1, 2, 3, 4, 5, 6};
int firstNode = node[0];
depthFirst(firstNode, 7);
}
public void depthFirst(int vFirst,int n)
{
int v,i;
st.push(vFirst);
while(!st.isEmpty())
{
v = st.pop();
if(isVisited[v]==0)
{
System.out.print("\n"+(v+1));
isVisited[v]=1;
}
for ( i=0;i<n;i++)
{
if((adjMatrix[v][i] == 1) && (isVisited[i] == 0))
{
st.push(v);
isVisited[i]=1;
System.out.print(" " + (i+1));
v = i;
}
}
}
}}
```
- elle a effectivement travaillé quand j'ai juste changé int[] nœud de 0 à 6 ans. En outre firstnode je n'ai même pas besoin de l'int[] nœud. Merci pour l'aide.
- Saurabh, je viens de tester ton code et il est en cours d'impression 1,2,4,7,5,6,3 au lieu de 1, 2, 4, 7, 3, 5, 6. Pouvez-vous svp tester et confirmer?
InformationsquelleAutor Saurabh

De travail/solution testée en C#, si quelqu'un à la recherche pour elle.

using System;
using System.Collections.Generic;
namespace GraphAdjMatrixDemo
{
public class Program
{
public static void Main(string[] args)
{
//0  1  2  3  4  5  6
int[,] matrix = {     {0, 1, 1, 0, 0, 0, 0},
{1, 0, 0, 1, 1, 1, 0},
{1, 0, 0, 0, 0, 0, 1},
{0, 1, 0, 0, 0, 0, 1},
{0, 1, 0, 0, 0, 0, 1},
{0, 1, 0, 0, 0, 0 ,0},
{0, 0, 1, 1, 1, 0, 0}  };
bool[] visitMatrix = new bool[matrix.GetLength(0)];
Program ghDemo = new Program();
for (int lpRCnt = 0; lpRCnt < matrix.GetLength(0); lpRCnt++)
{
for (int lpCCnt = 0; lpCCnt < matrix.GetLength(1); lpCCnt++)
{
Console.Write(string.Format(" {0}  ", matrix[lpRCnt, lpCCnt]));
}
Console.WriteLine();
}
Console.Write("\nDFS Recursive : ");
ghDemo.DftRecursive(matrix, visitMatrix, 0);
Console.Write("\nDFS Iterative : ");
ghDemo.DftIterative(matrix, 0);
Console.Read();
}
//====================================================================================================================================
public void DftRecursive(int[,] srcMatrix, bool[] visitMatrix, int vertex)
{
visitMatrix[vertex] = true;
Console.Write(vertex + 1 + "  ");
for (int neighbour = 0; neighbour < srcMatrix.GetLength(0); neighbour++)
{
if (visitMatrix[neighbour] == false && srcMatrix[vertex, neighbour] == 1)
{
DftRecursive(srcMatrix, visitMatrix, neighbour);
}
}
}
public void DftIterative(int[,] srcMatrix, int srcVertex)
{
bool[] visited = new bool[srcMatrix.GetLength(0)];
Stack<int> vertexStack = new Stack<int>();
vertexStack.Push(srcVertex);
while (vertexStack.Count > 0)
{
int vertex = vertexStack.Pop();
if (visited[vertex] == true)
continue;
Console.Write(vertex + 1 + "  ");
visited[vertex] = true;
for (int neighbour = 0; neighbour < srcMatrix.GetLength(0); neighbour++) 
//for (int neighbour = srcMatrix.GetLength(0) - 1; neighbour >= 0; neighbour--)//To make same as recursive
{
if (srcMatrix[vertex, neighbour] == 1 && visited[neighbour] == false)
{
vertexStack.Push(neighbour);
}
}
}
}
}
}

À faire ordre d'affichage des itératif de même que la récursivité, nous devons faire pression sur les voisins dans l'ordre inverse de la pile. A pris cette logique de Amit réponse ici

InformationsquelleAutor Sai

Vous devez vous connecter pour publier un commentaire.