[크래프톤 정글 5기] week02 알고리즘 주차 열네번째 날, 최소 스패닝 트리, 프림 알고리즘, 이분 그래프

신장 트리(Spanning Tree)

- 그래프 내의 모든 정점을 포함하면서 사이클이 없는 부분 트리

 

최소 스패닝(신장) 트리(Minimum Spanning Tree, MST)

- 가중치가 있는 양방향 그래프에서 싸이클 없이 모든 정점을 포함하며 가중치의 합이 최소인 트리

- 모든 정점을 연결하는 트리를 형성하면서, 가중치 합이 최소화되도록 하는 것

 

프림(Prim) 알고리즘

- 크루스칼 알고리즘과 더불어 그리디 알고리즘을 기반으로 최소 신장 트리를 구하는 대표적인 알고리즘

- 가중치가 작은 순으로 노드를 그래프에 포함시켜야 하기 때문에 우선순위 큐를 사용한다.

- 이미 그래프에 속한 노드엔 적용시키지 않기 위해 visited를 사용한다.

 

프림 알고리즘 동작원리

1. 임의의 시작 노드를 설정하고 T(트리)에 포함시킨다.

2. T에 있는 노드들의 인접 노드 중, 가중치가 가장 적고 방문하지 않은 노드를 T에 포함시킨다.

3. 2번을 반복한다.

 

프림 알고리즘 동작순서

1. 임의로 시작노드를 설정하고, 시작노드에 대한 인접노드와 비용을 우선순위 큐에 넣는다. (거리, 출발, 도착) 형태이다.

2. while문 시작, 큐에서 값을 pop하고(최소힙이기 때문에 가중치 작은게 알아서 나온다) 방문하지 않은 노드라면 방문체크 후 T(Tree)에 넣는다. 거리를 계산할거면 거리 변수에 거리도 추가하면 된다.

3. 방금 넣은 값들에 대한 다음 인접노드에 대하여 반복문을 돌려, 방문하지 않았을 경우 큐에 넣는다.

4. 2,3번을 반복한다.

 

 

이분 그래프(Bipartite Graph)

- 집합이 두 개 있을 때, 인접한 노드끼리 서로 다른 집합에 넣을 수 있다면 이분 그래프이다.

 

이렇게 인접한 노드끼리 서로 다른 집합에 들어가게 할 수 있다면 이분 그래프이다.

이분 그래프

 

이렇게 인접한 노드끼리 어찌해도 다른 집합에 속하게 할 수 없다면 이분 그래프가 아니다.

이분 그래프가 아님

 

 

이분 그래프인지 확인하는 방법

- DFS를 이용한다. DFS 함수를 호출할 때 group값을 인자로 함께 전달한다. ex) 1

- 인접노드에 대한 DFS 재귀호출을 할 때, group 값을 - group으로 준다. 이렇게 하면 현재 노드와 인접 노드는 각각 1, -1의 group 값을 가지게 된다.

- group 값은 visited에 저장한다. visited가 0이면(미방문이면) -group값과 함께 DFS를 호출하고, visited가 0이 아니면 현재 그룹값과 인접노드 그룹값을 비교하게 된다.

- 양방향이므로 그룹 값을 대입한 후 1번씩 비교해보는 과정을 거치며, 모든 노드를 다 돌면 자연스럽게 DFS 함수는 종료된다.

- 이 때 중간에 한번이라도 group값이 인접노드와 동일했다면 이분 그래프가 아니므로 즉시 False를 리턴하고 함수는 종료된다.

 

https://yskisking.tistory.com/192

이분 그래프를 찾는 백준 문제이다. 여기서 코드와 간략한 설명을 볼 수 있다.