[알고리즘 마스터] 9. 그래프 알고리즘 정리 (유니온 파인드, 위상정렬, 최단거리 알고리즘)

안녕하세요. 개발감자 박그냥입니다!🥔

오늘은 알고리즘 중 그래프 알고리즘에 대해 정리해보도록 하겠습니다.

1. 그래프의 알고리즘

1-1. 유니온 파인드

: 그래프의 사이클이 생성되는지 판별하는 알고리즘

 

1-2. 위상 정렬

: 그래프의 노드를 선형으로 정렬하는 알고리즘

• 조건 : 사이클이 없고, 방향이 있는 그래프인 경우에만 사용가능하다
• 특징 : 정렬했을 때 값이 유일하지 않을 수 있음
• 가장 많이 나오는 예시 : 수강신청  - 수1 -> 수2 (전후관계가 있음 = 방향이 있는)

 

1-3. 다익스트라

: 최단거리 알고리즘 - 시작점이 고정되어 있고, 다른 모든 노드로 가는 최단 거리를 구하는 알고리즘

• 조건 : 음수 간선이 있으면 안된다. ( 양수 간선이어야 함. 음수 가중치 안됨)
• 가장 많이 나오는 예시 : 음수간선이 없는 시작점이 고정된 경우 최단 거리,

1-4. 벨만 - 포드

: 최단거리 알고리즘 - 시작점이 고정되어 있고, 다른 모든 노드로 가는 최단 거리를 구하는 알고리즘

• 조건 : 음수 간선도 가능하다.
• 가장 많이 나오는 예시 : 음수간선이 있는 시작점이 고정된 경우 최단 거리  / 음수 사이클이 있는지 파악하는 경우

 

1-5. 플로이드 - 워셜

: 최단거리 알고리즘 - 시작점이 없고, 주어진 모든 노드의 최단 거리를 구하는 알고리즘

• 특징 : 시작점이 없다. 그래서 시간 복잡도가 좋지 않다.
• 가장 많이 나오는 예시 : 모든 도시 간의 최단 거리 구하기. (모든 키워드, 혹은 갯수가 한정되어 있는 경우 = 시간 복잡도 신경 안써도 되는)

 

1-6. 최소 신장 트리

:  모든 노드를 연결하는 데 최소 비용(최소의 가중치 합)으로 간선을 쓰는 알고리즘

• 특징 : 유니온 파인드가 필요하다. ( 사이클이 없음. = 트리는 사이클이 있을 수가 없음 / 사이클이 없게끔 방지해주는 역할)
• 가장 많이 나오는 예시 : 최소 비용으로 모든 노드를 연결하는 경우

 

그럼 더 유익한 포스팅으로 돌아올게요! 개발감자였습니다 :)