[DFS_BFS]-1260_DFS와 BFS

링크텍스트

인접행렬과 인접리스트를 사용하는 방법들 중 인접리스트를 이용하여 풀이 하였습니다.

인접행렬 인접리스트의 차이
인접행렬은 구현하기 매우 편리합니다. 노드의 연결관계를 알고 싶을때 adj[i][j]가 0인지 1인지 확인만 하면 되기 때문에 O(1)을 갖게 됩니다.(무방향에서는 0,0 | 1,1 | 2,2 ....| n.n 사이를 대각선을 두고 대칭을 이루게 됩니다. ) 하지만 정점이 어떤 한 노드에서 연결된 모든 노드를 방문 할 경우 adj[2]인 가로 행을 끝까지 돌아야 하므로 총 정점의 개수만큼 확인해보아야 하기 때문에 O(Vertax) 만큼 시간이 소요됩니다. 즉 정점이 많아짐에 따라 2차원 배열의 크기는 더욱 더 커지면서 많은 노드의 개수대로 확인을 해야하는 치명적인 문제가 발생합니다. 이러한 노드의 개수의 제약의 조금 더 효율적인 인접리스트 입니다. 노드가 1억개인데 간선이 10개도 안되는 경우, 이런경우 2차원 인접행렬을 쓰면 메모리 측면에서 비효율적인 측면을 갖게됩니다. 하지만 인접리스트는 해당 간선의 개수에 의존하여 생성되는 장점이자 단점을 가지고 있습니다. 즉 이말은 간선의 개수에 비례하여 메모리를 점유한다고 할 수 있습니다. 간선의 개수에 의존하므로 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;
                }
            }
        }

    }

}