그래프 내의 모든 정점을 포함하는 최소 연결 그래프로 부분 그래프

• 사이클이 없고 모든 노드가 이어져 있는 트리
• 사이클의 존재 여부가 트리와 그래프의 차이
• 그래프에서 사이클이 없는 것이 트리
  • 모든 노드로 가는 path를 최소화 하는 것이 minimum spanning tree

크루스칼 알고리즘

• 특징
  • 그래프 유형: 무방향, 가중치 그래프
  • 전략:
    • 출발: 간선을 가중치 기준으로 오름차순 정렬
    • 가장 가중치가 작은 간선부터 하나씩 선택
    • 사이클이 생기지 않도록 주의
    • 종료: V - 1개의 간선이 선택되면 종료
  • 흐름 개념
    • 모든 그래프들의 간선(edge)를 제거
    • 나머지 노드들 길이(cost)에 따라서 우선순위 큐에 edge를 다 넣음
    • 우선순위 큐가 빌때까지 반복
      • 우선순위 큐에서 dequeue
      • edge 끝점이 연결되어 있지 않으면 해당 모서리를 추가
      • 나머지 edges는 스킵
  • 시간 복잡도

    • 간선 정렬: O(E log E)

    • 사이클 검사 (Union-Find): 거의 O(1) (경로 압축 최적화 시)

    • 전체 시간 복잡도:

      ✅ O(E log E) (E: 간선 수)

프림(prim) 알고리즘

prim 알고리즘은 무방향 가중치 그래프에서 최소 신장 트리(MST)를 구하는 탐욕(Greedy) 알고리즘 이다.

• 특징
  • 그래프 유형: 무방향, 가중치 그래프
  • 전략
    • 출발: 임의의 정점에서 시작한다
    • 현재 MST에 연결된 간선 중 가중치가 가장 작은 간선을 선택한다.
    • 사이클이 생기지 않도록 주의한다.
    • 종료: 모든 정점이 MST에 포함될 때까지 반복한다.
  • 흐름 개념
    • 임의의 시작 정점을 선택하여 MST에 포함
    • 현재 MST와 연결된 모든 간선중 가장 작은 가중치 간선을 선택
    • 해당 간선으로 연결된 새 정점을 MST에 추가
    • 위 과정을 모든 정점이 포함될 때까지 반복
  • 시간 복잡도
    • 최소 힙(우선순위 큐) + 인접 리스트 방식
    • 정점 수: V, 간선 수: E
    • 간선 추가 시 우선순위 큐 연산: O(logV)
    • 모든 간선을 한 번씩 확인: O(E logV)
    • 최종 시간 복잡도:O(E logV)

정리