En ne retournant que les sommets dans le chemin le plus court
Je sais le titre est un peu brouillon, mais je ne sais pas comment l'expliquer mieux.
Ce que je suis en train de faire:
À l'aide d'un graphique trouvé dans un fichier texte, rechercher et imprimer le chemin le plus court (montant minimum de sommets) à partir du sommet A au sommet B.
Remarque: l'utilisation de largeur de recherche, pas de Dijkstra.
Ce que j'ai:
Un travail algorithme qui s'applique BFS sur le graphique, mais pas de bonne façon de réellement l'impression de le chemin le plus court.
Je vais avoir un moment difficile distinguer un sommet dans le chemin le plus court d'un qui est simplement de l'exécuter au moyen de l'algorithme, mais pas dans le chemin le plus court.
Par exemple: Trouver le chemin le plus court entre 0 et 4.
0 se connecte à 1,2 et 3. 1 se connecte à 4.
Mon chemin s'avère être [0,1,2,3,4] au lieu de [0,1,4].
Je n'ai pas été en mesure de trouver tous les threads poser la même question, ou tout au travers de BFS qui comprend cela, alors je ne sais pas si je suis en train de faire ce pour être façon plus difficile qu'elle ne l'est?
Edit: code pour ceux qui pourraient être intéressés (pas sûr du tout si je suis en évitant les cercles?)
Edit 2: Changé la façon dont je conserver mon chemin à une Pile.
public String findPath(int v, int w) {
Queue<Integer> q = new LinkedList<Integer>();
boolean[] visited = new boolean[g.numVertices()];
q.add(v);
Stack<Integer> path = new Stack<Integer>();
while(q.peek() != null) {
runBFS(q.poll(),w,visited,q,path);
}
return path.toString();
}
private void runBFS(int v, int w, boolean[] visited, Queue<Integer> q, Stack<Integer> path) {
if(visited[v]) {
}
else if(v == w) {
path.add(v);
q.clear();
}
else {
path.add(v);
visited[v] = true;
VertexIterator vi = g.adjacentVertices(v);
while(vi.hasNext()) {
q.add(vi.next());
}
}
}
Quelques explications de variables et de méthodes:
v = vertex d'origine
w = cible vertex
g = graphique
vi = normal d'un itérateur qui effectue une itération sur les voisins de v
Merci pour la lecture!
Comment est votre graphe représenté dans votre code? Comment éviter de faire des cercles? Il existe assez peu de questions de ce genre qui serait le mieux répondu par vous poster quelques de votre code...
J'ai ajouté un peu de code. Si il manque des infos sur le graphique laissez-moi savoir.
Je pense qu'il manque quelques choses ici. Pour l'un, ne sont pas
String
objets en Java immuable? A quoi bon changer path
dans runBFS
faire?Vous avez tout à fait raison, mon mauvais. J'ai cependant changé de Chaîne pour Pile à l'heure et apporter les modifications appropriées dans le code.
OriginalL'auteur bjrnt | 2011-03-28
Vous devez vous connecter pour publier un commentaire.
Vous devrez spécifique sur le champ chemin d'accès pour chaque sommet. De cette façon, vous pouvez conserver une trace des chemins que vous avez choisie, d'où le court chemin qui se trouve. Je vais utiliser un tableau de Chaîne, tout comme vous avez utilisé le Booléen tableau pour stocker visités sommets.
Génial! Exactement ce que je cherchais.
OriginalL'auteur jCoder
Un autre compact (espace-sage) de la solution que nous adjoints ont suggéré de ne pas utiliser O(n^2) d'espace de stockage, chaque nœud de stocker uniquement le nœud qui il vient. Cela peut être fait en changeant la visite-liste à un tableau d'entiers (
int[] visited
).etape 1: initialiser visité liste, de sorte que chaque élément est
'-1'
, ou "inconnu"étape 2: sélectionnez le premier noeud visité par lui-même
visited[v] = v;
Faire un BFS (comme vous le faites, avec les modifications suivantes:)
en cas de déplacement à partir de v -> v_next:
De cette façon, si w est accessible, visité[w] sera en magasin le nœud qui il est venu, à partir de ce nœud, vous pouvez revenir en arrière tout le chemin du retour à v et enfin de les imprimer dans l'ordre inverse. (Cela se fait soit à l'aide d'une pile ou d'une récursif de la méthode d'impression.)
L'espoir qui fait sens. 🙂
OriginalL'auteur pbos
Lorsque vous stockez un sommet dans la SECTION file d'attente, vous avez également besoin de stocker une copie de la voie par laquelle il a été atteint, de sorte qu'il sera disponible une fois que le sommet est retiré. Comme il est maintenant, votre code ne pas garder tout type de chemin d'informations sur la file d'attente des sommets - il ne conserve qu'une liste de nœuds qu'il visite.
Vous pourriez, par exemple, utiliser une file d'attente qui seront traitées en parallèle dans lequel vous allez stocker le chemin d'accès actuel, puis les restaurer une fois que vous dequeue le sommet suivant de la recherche.
OriginalL'auteur thkala
Vous avez besoin de pousser votre nœud actuel sur une pile, et de n'imprimer l'ensemble de la pile une fois que vous atteignez la destination.
Avez-vous été popping il lorsque vous avez sauvegardé?
OriginalL'auteur regularfry