[Algorithm] 무 방향 Graph의 Component 찾기

🎯 목표 : 주어진 무 방향 그래프의 간선 목록을 가지고 인접 행렬을 구현하고 DFS 탐색 방식으로 Component의 갯수를 찾는 알고리즘 작성.

📒 Find Component Count

📌 해결할 문제

• 인자로 주어진 무 방향 Graph의 간선 목록을 가지고 Component를 갯수를 반환.

📌 알고리즘

• 무 방향 Graph의 간선 목록이 인자로 주어진다.
• 간선 목록중 최대값은 Vertex의 최대값으로 정의하고, Vertex는 0부터 시작한다.
• 간선 목록을 가지고 인접 행렬을 정의한다.
• 인접 행렬을 DFS 방식의 탐색을 구현한다.
• DFS는 재귀 호출을 사용하여 구현.
• 모든 접점을 방문할때까지 탐색 하기 위해  모든 Vertex를 방문하고 행렬의 모든 요소들을 탐색한다.
• 행렬의 모든 요소를 방문할때 관계가 있는 Vertex들만 따로 배열에 수집하고, 수집한 Vertex가 그룹을 이룰때 count한다. - Component 카운트

📌 알고리즘 구현

• 관계가 있는 Vertex마다 Component를 지정해줄 변수 value.
• Component 카운터 변수 count.
• 간선 목록중 최대값을 가진 Vertex를 저장할 변수 max.
• 각 관계가 있는 Vertex를 수집할 배열 collect.
• 행렬을 저장할 2차원 배열 adj.
• 간선 목록을 인자로 받는 countComponent 메소드.
• 두 간선이 연결 되어 있는지 boolean 반환 타입의 isLinked 메소드.
• DFS 탐색을 위한 재귀 호출 dfsRecur 메소드.

public class FindComponent {
private int max=0;
    private int [][] adj;
    private int [] collect;
    private int value = 0;
    private int count = 0; // 컴포넌트 갯수 카운트

    public int countComponent(int[][] edges) {

        for (int[] edge : edges) {
            if (edge[0] > max) {
                max = edge[0];
            }
            if (edge[1] > max) {
                max = edge[1];
            }
        }
        adj = new int[max+1][max+1];
        collect = new int[max+1];
        for (int[] ints : adj) { // 행렬과 배열에 모든 값을 0으로 초기화
            Arrays.fill(collect,0);
            Arrays.fill(ints, 0);
        }
        for (int[] i : edges) { // 인자로 받은 간선 목록을 가지고 행렬에 추가
            adj[i[0]][i[1]] = 1;
            adj[i[1]][i[0]] = 1;
        }
        findComponent(); // 컴포넌트 갯수 카운터 호출
        return count;

    }

    // 행렬을 받아 두 정점이 이어져 있는지 확인
    private boolean isLinked(int[][] adj,int from, int to){
        return adj[from][to]==1&&adj[to][from]==1;
    }

    // DFS 순회
    private void dfsRecur(int v){
        /* vertex 만큼의 길이를 가진 배열을
        *  하나하나 방문할때 체크 하며 count와 동일한 value를 배열에 넣어준다
        *  각 vertex 마다 몇번째 Component에 속하는지 표시*/
        collect[v] = value;
        // vertex 갯수 만큼 순회
        for(int i=0; i<collect.length; i++){
            // 두 정점이 이어져있고, vertex에 방문한적이 없다면 재귀 호출
            // 정점이 이어져있지 않다면, 다음 요소 까지 재귀호출을 하지 않는다.
            // 재귀 호출을 하지 않았다는건,
            // i의 해당 요소가 매개 변수에 해당하는 vertex와 연결되어 있지 않았거나,
            // i에 해당하는 vertex에 방문한적이 있기 때문.
            if(isLinked(adj,v,i)&&collect[i]==0){
                dfsRecur(i);
            }
        }

    }
    // Vertex 별로 순회 해줌
    private void findComponent(){
        count = 0;
        Arrays.fill(collect,0); // 배열 초기화

        for(int i =0; i<collect.length; i++){
            // 해당 vertex에 방문한적이 없다면
            if(collect[i]==0){
                value++;
                dfsRecur(i);
                count++;
            }
        }
    }
}