Algorithmusimplementierung der Tiefendurchquerung und Breitendurchquerung des Baums in js

In diesem Artikel geht es um die Algorithmusimplementierung der Tiefendurchquerung und Breitendurchquerung von Bäumen. Ich hoffe, dass er für Freunde in Not hilfreich ist Du.

// Tiefendurchquerung

Algorithmusbeschreibung:

(1) Besuchen Sie Knoten v.

(2) Finden Sie den ersten benachbarten Punkt w von v.

(3) Wenn der angrenzende Punkt w existiert und nicht besucht wurde, beginnen Sie bei w und durchlaufen Sie den Graphen mit der Tiefe zuerst; andernfalls enden Sie.

(4) Finden Sie den nächsten benachbarten Punkt des Scheitelpunkts v in Bezug auf w und fahren Sie mit (3) fort.

function dfs (node) {
console.log(node); // 访问node
for(var i=0;i<node.children.length;i++) {
dfs(node.children[i]);
}
}

// Breitenorientierte Durchquerung

Algorithmusbeschreibung:

(1) Angenommen, der Anfangszustand von Graph G ist, dass nicht alle Scheitelpunkte besucht wurden, setze Hilfs Warteschlange Q, Warteschlange Q ist leer.

(2) Wählen Sie einen nicht besuchten Scheitelpunkt v als Ausgangspunkt für die Durchquerung.

(3) Besuchen Sie v, stellen Sie v in die Warteschlange und markieren Sie v als besucht.

(4) Wenn die Warteschlange Q nicht leer ist, nehmen Sie einen Scheitelpunkt v heraus.

(5) Finden Sie alle nicht besuchten benachbarten Punkte vi von v und besuchen Sie sie, fügen Sie sie in die Warteschlange ein und fahren Sie mit (4) fort, bis die Warteschlange leer ist.

(6) Wenn zu diesem Zeitpunkt noch nicht besuchte Knoten vorhanden sind, fahren Sie mit (2) fort, andernfalls beenden Sie den Vorgang.

var visited = []; // 访问过的
var arr = []; // 辅助队列,记录本层遍历的
var nextRound = []; // 下一层需要的遍历
function bfs () {
arr = nextRound;
nextRound = [];
for(var i=0;i<arr.length;i++) {
visited.push(arr[i]); // 访问arr[i]
for(var j=0;j<arr[i].children.length;i++) {
nextRound.push(arr[i].children[j]);
}
}
}
while(nextRound.length) {
bfs();
}

Verwandte Empfehlungen:

JS durchläuft die Schlüssel-Wert-Paare im Json-String, konvertiert sie zunächst in JSON-Objekte und durchläuft dann_Javascript-Fähigkeiten

JavaScript implementiert Pre-Order-, In-Order- und Post-Order-Traversal-Methoden von Binärbäumen

Das obige ist der detaillierte Inhalt vonAlgorithmusimplementierung der Tiefendurchquerung und Breitendurchquerung des Baums in js. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!