[Algorithm] Kruskal Algorithm (크루스칼 알고리즘)

2021. 2. 17. 21:49·스터디/Algorithm
728x90

💡크루스칼 알고리즘이란?

Greedy 알고리즘으로 MST(Minimum Spannig Tree, 최소 신장 트리) 문제 해결할 때 사용하는 알고리즘. 변의 개수를 E, 꼭짓점의 개수를V라고 하면 이 알고리즘은(Elog V)의 시간복잡도를 가진다.

즉, 모든 노드를 최소한의 비용으로 연결만 시키면 되기 때문에 간선의 비용을 오름차순으로 정렬 후 비용이 작은 간선부터 차례로 노드를 연결한다.

 

📌최소 신장 트리 구성 과정

1. 간선의 비용을 기준으로 정렬

2. 정렬된 순서에 맞게 최소 비용 순으로 그래프 연결

3. 연결 전 사이클이 발생하는지 확인

4. 사이클이 발생하는 경우 그래프에 포함하지 않음.

5. 위 과정을 반복

 

  • 스패닝 트리 : 1) 모든 노드(정점)을 포함하고, 2) 노드간 연결되어 있으며 사이클을 발생하지 않는 그래프
  • 최소 스패닝 트리 : 스패닝 트리 중에 선택한 간선의 가중치의 합이 최소인 트리

참고자료 : https://g.co/kgs/rur57B


💻관련문제

섬 연결하기 : programmers.co.kr/learn/courses/30/lessons/42861

728x90

'스터디 > Algorithm' 카테고리의 다른 글

[Algorithm] Binary Search (이분 탐색)  (0) 2021.02.26
자료형 크기 및 범위 정리  (0) 2021.02.26
[Algorithm] Priority Queue (우선순위 큐)  (0) 2021.02.17
[Algorithm] Segment Tree (세그먼트 트리)  (0) 2021.02.11
[Algorithm] Floyd-Warshall Algorithm  (0) 2021.02.07
'스터디/Algorithm' 카테고리의 다른 글
  • 자료형 크기 및 범위 정리
  • [Algorithm] Priority Queue (우선순위 큐)
  • [Algorithm] Segment Tree (세그먼트 트리)
  • [Algorithm] Floyd-Warshall Algorithm
zoodi
zoodi
IT/개발 관련 지식을 기록하는 블로그입니다.
  • zoodi
    오늘의 기록
    zoodi
  • 전체
    오늘
    어제
    • 분류 전체보기
      • 후기
        • 컨퍼런스
        • 일상리뷰
      • 금융경제
        • 뉴스
        • 금융IT용어
        • 경제 및 부동산
      • 코딩 테스트
      • 스터디
        • JAVA
        • Kotlin
        • Spring
        • React, Nextjs
        • 인공지능 AI
        • Cloud & k8s
        • Kafka
        • Database
        • Network
        • Algorithm
        • Hadoop
        • LINUX
        • R Programming
        • 기타 (소공, 보안)
      • 도서
      • 기타
  • 블로그 메뉴

    • 홈
    • 스터디
    • 금융경제
    • 후기
    • 기타
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    codility
    LeetCode
    이분탐색
    스프링
    카카오코테
    Python
    db
    kafka
    알고리즘
    금융용어
    C++
    java
    코테공부
    스프링부트
    pythoncodingtest
    Kotlin
    프로그래머스
    네트워크
    Spring
    코테
    CodingTest
    springboot
    MySQL
    코딩
    코딜리티
    리트코드
    자료구조
    자바
    코딩테스트
    쿠버네티스
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.4
zoodi
[Algorithm] Kruskal Algorithm (크루스칼 알고리즘)
상단으로

티스토리툴바