BFS/DFS
グラフィックを参照するには、BFSとDFSを使用します.
グラフとは?頂点(ノード)およびその頂点を接続する幹線(エッジ)からなる資料構造. グラフィックナビゲーション>1つの頂点から順にすべての頂点 にアクセスします.
まず、頂点と同じレベルにあるノードを参照します.
(できるだけ広く移動し、移動を継続できない場合は下に移動)
の2つのキューを使用します. 本に近いノードから探すため,最短距離の探索に有用である. targetがルートに近いと予想される場合に使用します. キュー実装 地図アプリケーションから特定の場所への最短距離ガイド おすすめ友達 検索範囲は大きくなく、検索起点から遠くない
時の子供たちが先に探る方法
(できるだけ深く、深く入るところがなければ横に移動)
は、1つのキューと1つのスタックを使用します. ノード(または任意のノード)から開始し、次の四半期までに ブランチを完全にナビゲートします. BFSよりも簡単に実施できるが、探索速度はBFSよりも 遅い.は再帰的またはスタックによって を実現する.
すべてのノードにアクセスする場合は、 にアクセスします.迷宮ゲームで経路が存在するか否かを判別する際に非常に有用である .パスの特徴を格納する必要がある場合(aからbまでのパスを探し、パスに同じ数字がないなど)、 .検索するグラフィックが非常に大きい場合は、 を考慮してください.
コメントとソース1
コメントとソース2
コメントとソース3
グラフとは?
幅優先ナビゲーション
コンセプト
まず、
(できるだけ広く移動し、移動を継続できない場合は下に移動)
特長
使用例
const graph = {
A: ["B", "C"],
B: ["A", "D"],
C: ["A", "G", "H", "I"],
D: ["B", "E", "F"],
E: ["D"],
F: ["D"],
G: ["C"],
H: ["C"],
I: ["C", "J"],
J: ["I"]
};
const bfs = (graph, startNode) => {
let visited = []; // 탐색을 마친 노드들
let needVisit = []; // 탐색해야할 노드들
needVisit.push(startNode); // 노드 탐색 시작
while (needVisit.length !== 0) { // 탐색해야할 노드가 남아있다면
const node = needVisit.shift(); // queue이기 때문에 선입선출, shift()를 사용한다.
if (!visited.includes(node)) { // 해당 노드가 탐색된 적 없다면
visited.push(node);
needVisit = [...needVisit, ...graph[node]];
}
}
return visited;
};
console.log(bfs(graph, "A"));
// ["A", "B", "C", "D", "G", "H", "I", "E", "F", "J"]
深度優先ナビゲーション
コンセプト
(できるだけ深く、深く入るところがなければ横に移動)
特長
使用例
const graph = {
A: ["B", "C"],
B: ["A", "D"],
C: ["A", "G", "H", "I"],
D: ["B", "E", "F"],
E: ["D"],
F: ["D"],
G: ["C"],
H: ["C"],
I: ["C", "J"],
J: ["I"],
};
// (graph, 시작 정점)
const dfs = (graph, startNode) => {
let needVisitStack = []; // 탐색을 해야 할 노드들
let visitedQueue = []; // 탐색을 마친 노드들
needVisitStack.push(startNode);
// 탐색을 해야 할 노드가 남아 있다면
while (needVisitStack.length !== 0) {
const node = needVisitStack.pop();
if (!visitedQueue.includes(node)) {
visitedQueue.push(node);
needVisitStack = [...needVisitStack, ...graph[node]];
}
}
return visitedQueue;
};
console.log(dfs(graph, "A"));
// ["A", "C", "I", "J", "H", "G", "B", "D", "F", "E"]
🔺BFSもDFSもノード数+幹線数の複雑さを持つ.コメントとソース1
コメントとソース2
コメントとソース3
Reference
この問題について(BFS/DFS), 我々は、より多くの情報をここで見つけました https://velog.io/@skdud4659/BFS-DFSテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol