18強DFSアルゴリズム

16465 ワード

深度優先検索(DFS)


  • 深度優先ナビゲーション
    (グラフィックで深部を優先的にブラウズするアルゴリズム)

  • DFSスタック構造(または再帰関数)の使用
    リファレンス
    スタックライブラリを使用する必要はありません.コンピュータ(関数)は構造的にスタック原理をよく使うからだ.
    したがって、スタックライブラリを使用するよりも、再帰関数を使用します.
  • ナビゲーション開始ノードをスタックに挿入し、アクセス処理を行う.
  • スタックの最上位ノードにアクセスされていない隣接ノードがある場合、アクセス処理はスタックに格納されます.アクセスされていない隣接ノードがない場合は、スタックから最上位ノードを取り出します.
  • ステップ
  • は、第2のプロセスが実行されなくなるまで繰り返される.
    アクセス基準の質問への提出
    注:操作手順
  • 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);
        }
    }