JSでのツリーの深さ優先トラバーサルと幅優先トラバーサルのアルゴリズム実装

この記事の内容は、js でのツリーの深さ優先トラバーサルと幅優先トラバーサルのアルゴリズムの実装に関するものです。必要な方は参考にしていただければ幸いです。

// 深さ優先トラバーサル

アルゴリズムの説明:

(1) ノード v を訪問します。

(2) v の最初の隣接点 w を求めます。

(3) 隣接する点 w が存在し、訪問されていない場合は、w から開始してグラフを深さ優先で走査し、それ以外の場合は終了します。

(4) w に関して頂点 v の次の隣接点を求め、(3) に進みます。

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

//幅優先走査

アルゴリズムの説明:

(1) グラフ G の初期状態は、すべての頂点が訪問されておらず、補助キュー Q を設定し、キュー Q が空であると仮定します。

(2) トラバースの開始点として未訪問の頂点 v を選択します。

(3) v を訪問し、v をキューに入れ、v を訪問済みとしてマークします。

(4) キューQが空でなければ、頂点vを取り出す。

(5) v の未訪問の隣接点 vi をすべて見つけてアクセスし、それらをキューにマージし、キューが空になるまで (4) に進みます。

(6) この時点でまだ訪問していないノードがある場合は(2)に進み、ない場合は終了します。

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

関連する推奨事項:

JS は、Json 文字列内のキーと値のペアを走査し、まずそれらを JSON オブジェクトに変換し、次に traverses_javascript スキル

JavaScript は、事前順序、順序内、および順序後の走査を実装します。二分木のメソッド

以上がJSでのツリーの深さ優先トラバーサルと幅優先トラバーサルのアルゴリズム実装の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。