18強DFSアルゴリズム
16465 ワード
深度優先検索(DFS)
深度優先ナビゲーション
(グラフィックで深部を優先的にブラウズするアルゴリズム)
DFSスタック構造(または再帰関数)の使用
リファレンス
スタックライブラリを使用する必要はありません.コンピュータ(関数)は構造的にスタック原理をよく使うからだ.
したがって、スタックライブラリを使用するよりも、再帰関数を使用します.
アクセス基準の質問への提出
✅ 注:操作手順
DFSソースの例
import java.util.*;
public class Main {
// visited, graph : 노드 번호가 1번부터 시작하므로 0번 인덱스는 비워둔다.
// 각 노드가 방문된 정보를 표현 (1차원)
public static boolean[] visited = new boolean[9];
// 각 노드가 연결된 정보를 표현 (2차원)
public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
// DFS 함수 정의
public static void dfs(int x) {
// 현재 노드를 방문 처리
visited[x] = true;
System.out.print(x + " ");
// 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for (int i = 0; i < graph.get(x).size(); i++) {
int y = graph.get(x).get(i);
if (!visited[y]) dfs(y);
}
}
public static void main(String[] args) {
// 그래프 초기화
for (int i = 0; i < 9; i++) {
graph.add(new ArrayList<Integer>());
}
// 노드 1에 연결된 노드 정보 저장
graph.get(1).add(2);
graph.get(1).add(3);
graph.get(1).add(8);
// 노드 2에 연결된 노드 정보 저장
graph.get(2).add(1);
graph.get(2).add(7);
// 노드 3에 연결된 노드 정보 저장
graph.get(3).add(1);
graph.get(3).add(4);
graph.get(3).add(5);
// 노드 4에 연결된 노드 정보 저장
graph.get(4).add(3);
graph.get(4).add(5);
// 노드 5에 연결된 노드 정보 저장
graph.get(5).add(3);
graph.get(5).add(4);
// 노드 6에 연결된 노드 정보 저장
graph.get(6).add(7);
// 노드 7에 연결된 노드 정보 저장
graph.get(7).add(2);
graph.get(7).add(6);
graph.get(7).add(8);
// 노드 8에 연결된 노드 정보 저장
graph.get(8).add(1);
graph.get(8).add(7);
dfs(1);
}
}
Reference
この問題について(18強DFSアルゴリズム), 我々は、より多くの情報をここで見つけました https://velog.io/@jhjcoding/18강-DFS-알고리즘テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol