Mit BFS-Algorithmus, um den kürzesten Weg zu finden

DFS-und BFS sind im wesentlichen die gleichen algorithmen. Der trick ist, die Daten-Struktur, die Sie verwenden, oder eher die Knoten, die Sie erkunden zuerst.

Einer Tiefe-zuerst-Suche nutzt einen stack und würde damit gehen so weit unten wie möglich, bevor Sie zurück in den Algorithmus.

Nutzen eine Breite erste Suche, würden Sie brauchen, um eine Warteschlange von Knoten, und von jedem Knoten aus, fügen Sie Ihren Nachbarn (wenn nicht bereits besucht), um die Warteschlange, und dann den rest des übergeordneten Knotens Nachbarn, bevor Sie fortfahren ab.

Wäre es nicht zu einer drastischen Veränderung des Codes, nur eine änderung in, wie man Knoten aus der Liste.

Statt knallen die Weg von der Rückseite würde Sie benutzen Sie einfach q.pop_front() um Ihren Knoten.

InformationsquelleAutor ardent

Für Die Suche Nach Kürzesten Weg
(Geschrieben in C++ /C++11)

Ich denke, dass dies wichtig, um hier hinzufügen, vor allem, weil der Titel ist auf kürzesten Wege! (der code unten, die tatsächlich ermöglichen, Sie zu finden)
Zusätzlich:
Wie oben erwähnt (in den Kommentaren zu der zweiten Antwort) DFS-und BFS sind ziemlich viel nicht(!) die gleichen algorithmen, die die ähnlichkeit im code ersetzen den stack mit einem queue und so dass Sie springen von einem zum anderen macht Sie nicht "im wesentlichen gleich". Das BFS ist bei weitem die bessere/richtige (zwischen den beiden), um den kürzesten Weg zu finden in einem ungewichteten Graphen. Das BFS ist der Aufbau von Schichten aus der Quelle und DFS geht so tief wie möglich.

Eigentlich beim laufen BFS (um den kürzesten Weg zu finden) sollten Sie die initialize-Knoten mit "Abstand" - parameter mit einer sehr großen Anzahl und statt mit der besuchten DS, aktualisieren Sie es, um die Eltern Abstand + 1 (nur wenn es noch mit dem Wert initialisiert).

Einen einfach Beispiel wäre:

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;
const int imax = std::numeric_limits<int>::max();
using vi = vector<int>;

/* printPath - implementation at the end */    
void
printPath(int s, int t, const vi &path);

/*input:
* n is number of the nodes in the Graph
* adjList holds a neighbors vector for each Node
* s is the source node
*/

void dfs(int n, vector<vi> adjList, int s)
{
    //imax declared above as the max value for int (in C++)
    vector<int> distance(n, imax);
    vi path;
    queue<int> q; q.push(s); distance[s] = 0;

    while (!q.empty()) {
        auto curr = q.front(); q.pop();

        for (int i = 0; i < (int)adjList[curr].size(); ++i) {
            if (distance[i] == imax) {
                distance[i] = distance[curr] + 1;
                //save the parent to have the path at the end of the algo.
                path[i] = curr;
            }
        }//for
    }//while
     /* t can be anything you want */
    int t = 5;
    printPath(s, t, path); cout << endl;
}

/* print the shortest path from s to t */ 
void
printPath(int s, int t, const vi &path)
{
    if (t == s) {
        return;
    }
    printPath(s, path[t], path);
    cout << path[t];
}

Inspiriert durch Steven & Felix, von:
Wettbewerbsfähige Programmierung 3

InformationsquelleAutor Kohn1001