Union-Find(합집합 찾기) 알고리즘

Union-Find 특징

• 대표적인 그래프 알고리즘으로 합집합 찾기라고도 불린다.
• 여러개의 노드가 존재할때 두 개의 노드가 같은 그래프에 속하는지 판별하는 알고리즘

 

코드

/**
 * 대표적인 그래프 알고리즘 Union-Find (합집합 찾기)
 * 
 * 여러개의 노드가 존재할때 두 개의 노드를 선택해서 같은 그래프에 속하는지 판별하는 알고리즘
 */
function solution()
{
    /**
     * 배열의 인덱스는 노드 번호를 뜻하고
     * 배열의 인덱스의 값은 부모 노드를 의미한다.
     * 
     * 최초 배열에는 자기 자신이 부모 노드로 존재한다.
     */
    let arr = [];
    for (let i = 1; i <= 10; i++)
        arr[i] = i;

    unionParent(arr, 1, 2);
    unionParent(arr, 2, 3);
    unionParent(arr, 3, 4);
    unionParent(arr, 5, 6);
    
    console.log(arr);
    
    console.log(findParent(arr, 1, 2)); // true
    console.log(findParent(arr, 1, 3)); // true
    console.log(findParent(arr, 1, 3)); // true
    console.log(findParent(arr, 4, 5)); // false
}

// 부모 노드를 찾는 재귀함수
function getParent(arr, x)
{
    if (arr[x] === x) return x;
    return arr[x] = getParent(arr, arr[x]);
}

// 두 개의 노드를 같은 부모 노드로 합친다.
function unionParent(arr, a, b)
{
    a = getParent(arr, a);
    b = getParent(arr, b);

    // 두 노드 중 작은 부모 노드값을 가진 값으로 합친다.
    if (a < b)
        arr[b] = a;
    else
        arr[a] = b;
}

// 같은 부모 노드를 갖는지 확인한다.
function findParent(arr, a, b)
{
    a = getParent(arr, a);
    b = getParent(arr, b);
    
    if (a === b)
        return true;
    else
        return false;
}

console.log(solution());

 

 

참조

https://blog.naver.com/ndb796/221230967614