DFS/BFS-<2>ナビゲーションアルゴリズム

# DFS (Depth-First Search)

DFSは深さ優先探索とも呼ばれ,グラフィックにおける深さ優先探索のアルゴリズムである.探索を行うにはO(N)の時間が必要である.
💡DFS動作:スタック構造を使用する->再帰関数で実現!

ナビゲーション開始ノードをスタックに挿入し、アクセス処理を行う.

スタックの最上位ノードに未アクセスの隣接ノードがある場合は、その隣接ノード(1個)をスタック(通常は番号の低い順から入れる)に入れてアクセス処理を行う.
アクセスされていない隣接ノードがない場合は、スタックから最上位ノードを取り出します.

以上の手順

を繰り返し、これ以上実行できなくなるまで繰り返します.

import java.util.ArrayList;

public class DFSEx {
    // 방문 정보 저장할 리스트
    public static boolean[] visited = new boolean[9];
    // 그래프 저장할 인접 리스트 생성
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();

    // DFS 정의
    public static void dfs(int n) {
        // 현재 노드 방문처리
        visited[n] = true;
        System.out.print(n + " ");

        // 현재 노드와 연결된 다른 노드 재귀적으로 방문
        for(int i=0; i<graph.get(n).size(); i++) {
            int next = graph.get(n).get(i);
            if(!visited[next]) dfs(next);
        }
    }
    public static void main(String[] args) {
        // 그래프 노드 초기화
        for(int i=0; i<9; i++) {
            graph.add(new ArrayList<Integer>());
        }

        // 연결 정보 저장
        graph.get(1).add(2);
        graph.get(1).add(3);
        graph.get(1).add(8);
		...

        dfs(1);
    }
}

# BFS (Breadth First Serach)

BFSは幅優先探索とも呼ばれ,図形に最も近いノードから探索を開始するアルゴリズムである.ナビゲーションの実行にはO(N)の時間が必要であり,一般にDFSよりも実際の実行時間が良い.
💡BFS動作:キューリソース構造の使用

ナビゲーション開始ノードをキューに挿入し、アクセス処理を行う.

キューからノードを取り出し、そのノードの隣接ノードでは、アクセスされていないすべてのノードをキューに挿入してアクセス処理を行う.

以上の手順

を繰り返し、これ以上実行できなくなるまで繰り返します.

import java.util.*;

public class BFSEx {
    // 방문 정보 저장할 리스트
    public static boolean[] visited = new boolean[9];
    // 그래프 저장할 인접 리스트 생성
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();

    // BFS 함수 정의
    public static void bfs(int n) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(n); // 노드 큐에 집어넣기
        visited[n] = true; // 현재 노드 방문 처리

        while(!q.isEmpty()) {
            int next = q.poll();
            System.out.print(next + " ");
            // 현재 노드와 연결되어 있으면서 방문하지 않은 노드들 큐에 삽입
            for(int i=0; i<graph.get(next).size(); i++) {
                int linked = graph.get(next).get(i);
                if(!visited[linked]) {
                    q.offer(linked);
                    visited[linked] = true;
                }
            }
        }
    }
    
    public static void main(String[] args) {
        // 그래프 노드 초기화
        for(int i=0; i<9; i++) {
            graph.add(new ArrayList<Integer>());
        }

        // 연결 정보 저장
        graph.get(1).add(2);
        graph.get(1).add(3);
        graph.get(1).add(8);
		...

        bfs(1);
    }
    
}