スタックとキューでBFSとDFSアルゴリズムを実現する.
10038 ワード
スタックとキューでBFSとDFSアルゴリズムを実現する.
1.BFS(幅優先エルゴード)
1、頂点vから図Gを巡回するアルゴリズムは、①訪問V 0②は、最寄層のアクセス頂点がv 1 v 2 v 3 vkであると仮定して、順番にv 1、v 2、v 3…vkの未訪問隣接点③重複②訪問されていない隣接点がないことを知っているまでの2、心得:bfsアルゴリズムは、実は段階巡回アルゴリズムである.アルゴリズム記述から、キューというデータ構造を使用するアルゴリズムが見られます.Setセットの役割は、現在のノードがすでにアクセスされているかどうかを判断するために、キューに追加されてしまい、重複した追加を回避するために使用される.3、アルゴリズムコード:
1、頂点vから図Gのアルゴリズム①を巡回してvにアクセスする②頂点vが訪問されていない隣接点から順に深さを巡回する.2、心得:dfsアルゴリズムは通常、再帰的な特性を使用し、アルゴリズムコードを簡潔にする.再帰的にはアルゴリズムが分かりにくいので、ここではスタックを使って実現しています.分かりやすいです.
_.対応するステートメントには説明があります.Setセットはここでも、ノードが都スタックに追加されているかどうかを示しています.
3、アルゴリズムコード:
1.BFS(幅優先エルゴード)
1、頂点vから図Gを巡回するアルゴリズムは、①訪問V 0②は、最寄層のアクセス頂点がv 1 v 2 v 3 vkであると仮定して、順番にv 1、v 2、v 3…vkの未訪問隣接点③重複②訪問されていない隣接点がないことを知っているまでの2、心得:bfsアルゴリズムは、実は段階巡回アルゴリズムである.アルゴリズム記述から、キューというデータ構造を使用するアルゴリズムが見られます.Setセットの役割は、現在のノードがすでにアクセスされているかどうかを判断するために、キューに追加されてしまい、重複した追加を回避するために使用される.3、アルゴリズムコード:
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
public class Code_01_BFS {
public static void bfs(Node node) {
if (node == null) {
return;
}
Queue<Node> queue = new LinkedList<>();
HashSet<Node> map = new HashSet<>();//
queue.add(node);
map.add(node);
while (!queue.isEmpty()) {
Node cur = queue.poll();
System.out.println(cur.value);
for (Node next : cur.nexts) {
if (!map.contains(next)) {//map set
map.add(next);
queue.add(next);
}
}
}
}
}
2.DFSアルゴリズム(深さ優先エルゴード)1、頂点vから図Gのアルゴリズム①を巡回してvにアクセスする②頂点vが訪問されていない隣接点から順に深さを巡回する.2、心得:dfsアルゴリズムは通常、再帰的な特性を使用し、アルゴリズムコードを簡潔にする.再帰的にはアルゴリズムが分かりにくいので、ここではスタックを使って実現しています.分かりやすいです.
_.対応するステートメントには説明があります.Setセットはここでも、ノードが都スタックに追加されているかどうかを示しています.
3、アルゴリズムコード:
public class Code_02_DFS {
//
public static void dfs(Node node) {
if (node == null) {
return;
}
Stack<Node> stack = new Stack<>();
HashSet<Node> set = new HashSet<>();//
stack.add(node);
set.add(node);
System.out.println(node.value);
while (!stack.isEmpty()) {
Node cur = stack.pop();//
for (Node next : cur.nexts) {
//
if (!set.contains(next)) {// set
stack.push(cur);//
stack.push(next);
set.add(next);
System.out.println(next.value);//
break;
}
}
}