À l'aide de BFS algorithme pour trouver le chemin le plus court
std::list <int> q;
std::vector<bool> visited(cols + 1);
for(int i = 1; i <= cols; i++) visited[i] = false;
visited[x] = true;
if(!l[x].empty())
{
for(std::list<int>::iterator i = l[x].begin(); i != l[x].end(); i++)
{
q.push_back(x); q.push_back(* i);
}
while(!q.empty())
{
y = q.back(); q.pop_back();
x = q.back(); q.pop_back();
if(!visited[y])
{
visited[y] = true;
if(!l[y].empty())
for(std::list<int>::iterator i = l[y].begin(); i != l[y].end(); i++)
{
if(!visited[*i])
{q.push_back(y); q.push_back(* i);}
}
dfst[x].push_back(y);
if(flag != 0) dfst[y].push_back(x);
}
}
}
C'est mon DFS algorithme pour trouver le spanning tree dans un graphe. J'ai besoin de les convertir à l'algorithme BFS trouver le plus court chemin entre deux sommets. Eh bien...comment puis-je faire cela? Est l'algorithme BFS peu près semblable à celui ci-dessus? Ou dois-je besoin de l'écrire depuis le début?
l - liste d'adjacence
dfst - tableau holding spanning tree à la fin
x - a partir de vertex
y - helper variable
Vous devez vous connecter pour publier un commentaire.
DFS et BFS sont essentiellement les mêmes algorithmes. Le truc, c'est qui la structure de données que vous utilisez, ou plutôt qui les nœuds à explorer en premier.
Profondeur d'abord de recherche utilise une pile et serait donc aller aussi loin que possible, avant de revenir dans l'algorithme.
D'utiliser une largeur de recherche, vous avez besoin d'utiliser une file d'attente des nœuds, et d'explorer chaque nœud, ajouter leurs voisins (si pas déjà visité) à la file d'attente, puis de traiter le reste du parent du nœud voisins avant de continuer d'avancer.
Il ne serait pas un changement radical de votre code, il suffit d'un changement dans la façon de vous obtenir des nœuds à partir de votre liste.
Plutôt que de les voir apparaître sur le dos vous pouvez tout simplement utiliser
q.pop_front()
pour obtenir votre nœuds.BFS est similaire à DFS. Au lieu d'aller aussi profond que vous le pouvez, revenir en arrière et répéter, vous regardez tous les nœuds à la profondeur 1, alors tous les nœuds de profondeur 2, etc, jusqu'à ce que vous avez visité tous les nœuds.
Algorithme De Base:
Pour Trouver Le Chemin Le Plus Court
(Écrit en C++ /C++11)
Je pense que c'est important d'ajouter ici, surtout parce que le titre est sur chemins les plus courts! (le code ci-dessous qui effectivement vous permettre d'en trouver un)
En outre:
Comme mentionné ci-dessus (dans les commentaires pour la deuxième réponse) DFS et BFS sont quasiment pas(!) les mêmes algorithmes, la similitude dans le code de remplacement de la pile avec une file d'attente et vous permettant de sauter de l'un à l'autre n'est pas "essentiellement les mêmes". BFS est de loin le meilleur/droite (entre les deux) pour trouver le plus court chemin dans un graphe non pondéré. BFS est la construction de couches à partir de la source et de la ssr va aussi profondément que possible.
En fait lors de l'exécution de BFS (pour trouver le chemin le plus court), vous devez initialiser votre nœuds avec une "distance" paramètre avec un très grand nombre et au lieu d'utiliser la visité DS, vous le mettez à jour du parent à la distance + 1 (seulement si elle est toujours avec la initialisée valeur).
Un simple exemple serait:
Inspiré par Steven & Félix, à partir de:
Concurrentiel De Programmation 3
Non,vous n'avez pas à beaucoup de changement dans votre code. il suffit de remplacer de remplacer la pile en cas de DFS avec la File d'attente et il deviendra BFS.
Différence dans la mise en œuvre de la BFS et la DFS est que "BFS est mis en œuvre à l'aide de la File d'attente et DFS est à l'aide de la Pile" (la Raison est évident que DFS n'profondeur comme dans le labyrinthe.)
VOIR les changements par vous-même:
DFS:
BFS:
Comme vous pouvez le voir, la mise en œuvre de deux diffèrent juste "dans l'utilisation de la PILE et FILE d'attente".
Espérons que cette aide !