［DFS BFS］−1260 DFSおよびBFS

リンクテキスト
隣接行列と隣接リストを用いる方法では,隣接リストを用いて解いた.
隣接マトリクス隣接リストの違い
隣接マトリクスは非常に容易に実施できる.ノードの接続関係を理解するには、adj[i][j]が0であるか1であるかを判断するだけで、O(1)を持つことができます.(無方向上では0,0|1,1|2...|n.nの間で対角線対称を呈する.)ただし、あるノードから接続されているすべてのノードにアクセスする場合は、水平行(adj[2])を最後に迂回する必要があるため、各ノードの合計数をチェックする必要があるため、O(Vertax)と同じ時間がかかります.これは、頂点が増えるにつれて、2 D配列のサイズが大きくなることを意味し、複数のノードでチェックする必要があるという致命的な問題が発生します.これらのノード数制限のより効果的な隣接リスト.1億個のノードがあり、幹線が10本もない場合、2 D隣接マトリクスを使用するとメモリの効率が低下します.しかし、隣接リストの利点と欠点は、その幹線の数に依存することである.つまり、これは幹線の数に比例してメモリを消費する.幹線の数に依存するため、時間的複雑さはO(Edge)に相当する.iノードj図が接続されているかどうかを決定しようとすると、隣接マトリクスはadj[i][j]を直接介して検査することができる(O(1)).「隣接」リストでは、i番目のリストに接続されているノードの数でループするのが欠点です.

package oneDay_twoSol.DB_FirstSearch;

import java.util.*;

public class DFS_BFS {
    static ArrayList<ArrayList<Integer>> adjacentList = new ArrayList<>(); // 인접리스트
    static boolean visited[]; // 방문 여부 판단.

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int start_Vertax = sc.nextInt();
        sc.nextLine();
        for (int i = 0; i <= n; i++) {
            adjacentList.add(new ArrayList<Integer>());
        }
        for (int i = 1; i <= m; i++) {
            int a=sc.nextInt();
            int b=sc.nextInt();
            // 방향이 없는 그래프 특징.
            adjacentList.get(a).add(b);
            adjacentList.get(b).add(a);
        }
        for (int i = 1; i <=n; i++) {
            if(!adjacentList.get(i).isEmpty())
                Collections.sort(adjacentList.get(i));
        }
       /* for (int i = 0; i <adjacentList.size() ; i++) {
            System.out.println(adjacentList.get(i));
        }*/

        visited=new boolean[n+1];
        dfs(start_Vertax);
        visited=new boolean[n+1];
        System.out.println();
        bfs(start_Vertax);

    }

    static void dfs(int vertax) {
        System.out.print(vertax + " ");
        visited[vertax] = true;
        // ===== 방문함과 동시에 출력 =====
        for (int i = 0; i <adjacentList.get(vertax).size() ; i++) {
        //adjacentList.get(vertax) -> 해당 방문하는 노드의 인접리스트이 사이즈 만큼만 순회 (해당 정점과 연결되있는 노드만 탐색한다는 의미
            int temp=adjacentList.get(vertax).get(i);
                if (!visited[temp])
                {   dfs(temp); // 재귀적으로 함수 호출을 하는 DFS의 특징
                }
        }
    }
    // 재귀적으로 호출하는 성질인 DFS와는 다르게 큐의 삽입된 정점들을 차례대로 상대하는 특징을 가지므로 재귀적인 DFS와는 다른 특징.
    static void bfs(int vertax)
    {
        Queue<Integer> q=new LinkedList<>();
        q.offer(vertax);

        visited[vertax]=true;
        while (!q.isEmpty())
        {
            int temp=q.poll();
            System.out.print(temp+" ");
            for (int i = 0; i <adjacentList.get(temp).size() ; i++) {
                int v=adjacentList.get(temp).get(i);
                if(!visited[v])
                {
                    q.offer(v);
                    visited[v]=true;
                }
            }
        }

    }

}