Implémentation d'un algorithme de parcours en profondeur d'abord et en largeur d'abord de l'arbre en js

Ce que cet article vous apporte concerne l'implémentation de l'algorithme du parcours en profondeur et en largeur des arbres dans js. Il a une certaine valeur de référence. J'espère que cela sera utile. toi.

// Traversée en profondeur d'abord

Description de l'algorithme :

(1) Visitez le nœud v.

(2) Trouvez le premier point adjacent w de v.

(3) Si le point adjacent w existe et n'a pas été visité, commencez par w et parcourez le graphique en profondeur, sinon terminez.

(4) Trouvez le prochain point adjacent du sommet v par rapport à w et passez à (3).

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

// Parcours en largeur d'abord

Description de l'algorithme :

(1) Supposons que l'état initial du graphe G est que tous les sommets n'ont pas été visités , et définissez la file d'attente auxiliaire Q, la file d'attente Q est vide.

(2) Choisissez un sommet v non visité comme point de départ du parcours.

(3) Visitez v, mettez v dans la file d'attente et marquez v comme visité.

(4) Si la file d'attente Q n'est pas vide, retirez un sommet v.

(5) Trouvez tous les points adjacents non visités vi de v et visitez-les, fusionnez-les dans la file d'attente et passez à (4) jusqu'à ce que la file d'attente soit vide.

(6) S'il reste des nœuds non visités à ce moment, passez à (2), sinon terminez.

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();
}

Recommandations associées :

JS parcourt les paires clé-valeur dans la chaîne Json, convertissez-les d'abord en objets JSON, puis traversez_javascript en compétences

JavaScript implémente des méthodes de traversée en pré-ordre, dans l'ordre et après-ordre des arbres binaires

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!