👏 그래프란?

노드와 노드 사이에 연결된 간선의 저보를 가지고 있는 자료구조

문제에서 서로 다른 개체(혹은 객체)가 연결 되어 있다 라는 말이 있다면 그래프 알고리즘을 떠올려야 한다.

서로소 집합 자료구조(Union-Find)

1. union(합집합) 연산을 확인하여, 서로 연결된 두 노드 A,B 를 확인한다.
   1.1 A와 B의 루트 노드 A' B' 를 각각 찾는다
   1.2 A'를 B'의 부모 노드로 설정한다. (B'가 A'를 가리키도록 한다.)
2. 모든 union(합집합) 연산을 처리할 때까지 1번 과정을 반복한다.

✌ 서로소 집합을 활용한 사이클 판별

서로소 집합은 무방향 그래프 내에서의 사이클을 판별할 때 사용할 수있다는 특징이 있다.(같은 그룹을 한번 더 호출하면 cycle 발생 )
참고로, 방향 그래프 사이에서의 사이클 여부는 DFS를 통해 판별가능하다.

#include <iostream>
using namespace std;

char vect[200];

char getBoss(char tar)
{
    if (vect[tar] == 0) {
        return tar;
    }

    char ret = getBoss(vect[tar]);
    return ret;
}

void makeGroup(char t1, char t2)
{
    char a = getBoss(t1);
    char b = getBoss(t2);

    if (a == b) return;
    vect[b] = a;
}

int main()
{
    makeGroup('A', 'B');
    makeGroup('B', 'C');
    

    if (getBoss('A') == getBoss('C')) {
        cout << "같은그룹";
    }
    else
    {
        cout << "다른그룹";
    }

 	return 0;
}

경로 압축
char ret = getBoss(vect[tar]);

😊 신장 트리

신장 트리란, 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다.

😁 최소 신장 트리 (MST, 크루스칼 알고리즘)

최소한의 비용으로 신장트리를 찾고싶을 때 사용한다.

크루스칼 알고리즘을 사용하면 가장 적은 비용으로 모든 노드를 연결할 수 있는데 그리디 알고리즘으로 분류할 수 있다. 모든 간선에 대하여 정렬을 수행한 뒤에 가장 거리가 짧은 간선부터 집합에 포함시키면된다.(先 가중치 정렬 後 Unionfind 이용)

최종적으로 신장 트리에 포함되는 간선의 개수가 '노드의 개수 - 1' 과 같다.

😎 위상 정렬

위상 정렬이란 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것' 이다.

위상 정렬 알고리즘

1. 진입차수가 0 인 노드를 큐에 넣는다.
2. 큐가 빌 때까지 다음의 과정을 반복한다.
   I. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.
   II. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.

진입차수란 -> 특정한 노드로 들어오는 간선의 개수를 의미한다.

참고로, 위상정렬의 답안은 여러가지가 될 수 있다. (한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상일 경우)