Beginnen wir mit der Bemerkung, dass Breitensuche (BFS) die kürzesten Pfade von einem gegebenen Quellknoten berechnet, wenn der Graph nicht gewichtet ist. Mit anderen Worten, wir betrachten die Länge eines Pfades als die Anzahl der Kanten im Pfad.
Hier ist eine einfache Möglichkeit, eine ungewichtete Graphen zu konstruieren:
function Graph() {
var neighbors = this.neighbors = {}; // Key = vertex, value = array of neighbors.
this.addEdge = function (u, v) {
if (neighbors[u] === undefined) { // Add the edge u -> v.
neighbors[u] = [];
}
neighbors[u].push(v);
if (neighbors[v] === undefined) { // Also add the edge v -> u so as
neighbors[v] = []; // to implement an undirected graph.
} // For a directed graph, delete
neighbors[v].push(u); // these four lines.
};
return this;
}
Bitte beachte, dass wir einen ungerichteten Graphen umgesetzt haben. Wie in den Inline-Kommentaren erwähnt, können Sie den Code ändern, um einen gerichteten Graphen zu erstellen, indem Sie vier Zeilen aus der addEdge-Funktion löschen.
Diese Implementierung von BFS würde auf einem gerichteten Graphen gleich gut funktionieren:
function bfs(graph, source) {
var queue = [ { vertex: source, count: 0 } ],
visited = { source: true },
tail = 0;
while (tail < queue.length) {
var u = queue[tail].vertex,
count = queue[tail++].count; // Pop a vertex off the queue.
print('distance from ' + source + ' to ' + u + ': ' + count);
graph.neighbors[u].forEach(function (v) {
if (!visited[v]) {
visited[v] = true;
queue.push({ vertex: v, count: count + 1 });
}
});
}
}
Um den kürzesten Weg zwischen zwei vorgegebenen Eckpunkten zu finden und die Scheitelpunkte entlang des Weges zeigen, haben wir den Vorgänger von jedem Scheitelpunkt erinnern wie wir die Grafik erkunden:
function shortestPath(graph, source, target) {
if (source == target) { // Delete these four lines if
print(source); // you want to look for a cycle
return; // when the source is equal to
} // the target.
var queue = [ source ],
visited = { source: true },
predecessor = {},
tail = 0;
while (tail < queue.length) {
var u = queue[tail++], // Pop a vertex off the queue.
neighbors = graph.neighbors[u];
for (var i = 0; i < neighbors.length; ++i) {
var v = neighbors[i];
if (visited[v]) {
continue;
}
visited[v] = true;
if (v === target) { // Check if the path is complete.
var path = [ v ]; // If so, backtrack through the path.
while (u !== source) {
u = predecessor[u];
path.push(u);
}
path.reverse();
print(path.join(' → '));
return;
}
predecessor[v] = u;
queue.push(v);
}
}
print('there is no path from ' + source + ' to ' + target);
}
der folgende Ausschnitt zeigt, diese Vorgänge in der Grafik, die Sie in Ihrer Frage geben. Zuerst finden wir die kürzesten Wege zu allen Knoten, die von A erreichbar sind. Dann finden wir den kürzesten Weg von B zu G und von G zu A.
function Graph() {
var neighbors = this.neighbors = {}; // Key = vertex, value = array of neighbors.
this.addEdge = function (u, v) {
if (neighbors[u] === undefined) { // Add the edge u -> v.
neighbors[u] = [];
}
neighbors[u].push(v);
if (neighbors[v] === undefined) { // Also add the edge v -> u in order
neighbors[v] = []; // to implement an undirected graph.
} // For a directed graph, delete
neighbors[v].push(u); // these four lines.
};
return this;
}
function bfs(graph, source) {
var queue = [ { vertex: source, count: 0 } ],
visited = { source: true },
tail = 0;
while (tail < queue.length) {
var u = queue[tail].vertex,
count = queue[tail++].count; // Pop a vertex off the queue.
print('distance from ' + source + ' to ' + u + ': ' + count);
graph.neighbors[u].forEach(function (v) {
if (!visited[v]) {
visited[v] = true;
queue.push({ vertex: v, count: count + 1 });
}
});
}
}
function shortestPath(graph, source, target) {
if (source == target) { // Delete these four lines if
print(source); // you want to look for a cycle
return; // when the source is equal to
} // the target.
var queue = [ source ],
visited = { source: true },
predecessor = {},
tail = 0;
while (tail < queue.length) {
var u = queue[tail++], // Pop a vertex off the queue.
neighbors = graph.neighbors[u];
for (var i = 0; i < neighbors.length; ++i) {
var v = neighbors[i];
if (visited[v]) {
continue;
}
visited[v] = true;
if (v === target) { // Check if the path is complete.
var path = [ v ]; // If so, backtrack through the path.
while (u !== source) {
path.push(u);
u = predecessor[u];
}
path.push(u);
path.reverse();
print(path.join(' → '));
return;
}
predecessor[v] = u;
queue.push(v);
}
}
print('there is no path from ' + source + ' to ' + target);
}
function print(s) { // A quick and dirty way to display output.
s = s || '';
document.getElementById('display').innerHTML += s + '<br>';
}
window.onload = function() {
var graph = new Graph();
graph.addEdge('A', 'B');
graph.addEdge('B', 'C');
graph.addEdge('B', 'E');
graph.addEdge('C', 'D');
graph.addEdge('C', 'E');
graph.addEdge('C', 'G');
graph.addEdge('D', 'E');
graph.addEdge('E', 'F');
bfs(graph, 'A');
print();
shortestPath(graph, 'B', 'G');
print();
shortestPath(graph, 'G', 'A');
};
body {
font-family: 'Source Code Pro', monospace;
font-size: 12px;
}
<link rel="stylesheet" type="text/css"
href="https://fonts.googleapis.com/css?family=Source+Code+Pro">
<div id="display"></id>
Ich fürchte, ich verstehe nicht, wie man diese Funktion benutzt: wenn ich etwas wie var 'code' versuche, starte = myVertices [1]; var end = myVertices [5]; bfs (Ende); Ich bekomme eine Fehlermeldung, dass "graph [u] nicht definiert ist." Ich möchte nur einen Anfangs- und Endpunkt eingeben und einen einigermaßen direkten Weg einschlagen können. Macht das Sinn? – Tyler330
Vielen Dank für die erstaunliche Geschwindigkeit - wenn ich das schnell und genau codieren könnte, wäre ich ein glücklicherer Mensch. Das ist in etwa das, wonach ich suche: Nach Wochen, in denen ich A * versuchte, wurde mir klar, dass eigentlich ein einigermaßen direkter Weg besser funktionieren könnte, da dies Verkehrsstaus reduzieren würde. – Tyler330
Ich gab Ihnen eine generische BFS-Implementierung, anstatt zu versuchen, mit der Maschinerie dieser Diagrammbibliothek zu interagieren. Nachdem ich mir die Bibliothek angeschaut habe, sehe ich, was Sie damit meinen, wie schwierig es ist, damit zu arbeiten. Ich denke, es ist unnötig kompliziert. Bitte sehen Sie meine überarbeitete Antwort. Ich habe eine übersichtliche Graphimplementierung hinzugefügt und eine neue Breitensuche geschrieben, die den kürzesten Pfad zwischen zwei gegebenen Knoten anzeigt. –