그래프 알고리즘

Graph algorithm

<그래프에서 최소 비용 문제>

• 최소신장트리(Minimum Spanning Tree)

  - 프림(Prim) : 한 정점에서 연결된 간선들 중 최단거리를 선택해서 최소신장트리 구성

  - 크루스칼(Kruskal) : 최소 가중치 간선을 하나씩 선택해서 최소신장트리를 구성(사이클이 없어야 함)

    * 간선(edge)의 개수가 적은 경우에는 크루스칼, 간선의 개수가 많은 경우에는 프림 사용이 유리

• 최단경로

  • 단일 시작점 최단 경로 문제

    - 다익스트라(Dijkstra) : 음의 가중치를 허용하지 X

    - 벨만-포드(Bellman-Ford) : 음의 가중치 허용하지만 가중치의 합이 음인 사이클은 허용하지 X

  • 모든 쌍 최단 경로 문제

    - 플로이드-워샬(Floyd-Warshall)

 

1. 최소 신장 트리(MST : Minimum Spanning Tree)

  • 신장 트리는 n개의 정점을 포함하는 무향 그래프에서 n개의 정점과 n-1개의 간선으로 구성된 트리

  • 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리를 최소 신장 트리라고 함

  • 최소 신장 트리를 찾는 알고리즘으로 프림과크루스칼 알고리즘이 있음

2. 프림(Prim) 알고리즘

  • 프림 알고리즘은 한 정점에 연결된 간선들 중에서 하나의 간선을 선택하면서 최소 신장 트리를 만들어 가는 방식

    - 임의의 정점을 하나 선택해서 시작

    - 선택한 정점들과 인접하는 정점들 중에 최소 비용의 간선이 존재하는 정점을 선택

    - 모든 정점이 선택될 때까지 앞의 과정을 반복함

  • 정점을 하나씩 선택할 때 간선을 하나씩 추가하면서 트리를 확장함

3. 크루스칼(Kruskal) 알고리즘

  • 사이클이 생기지 않도록 최소 가중치 간선을 하나씩 선택하면서 최소 신장 트리를 찾는 알고리즘

    - N개의 정점을 포함하는 그래프에서 n-1개의 간선을 선택하는 방식

    - 간선을 선택해 나가는 과정에 여러 개의 트리들이 존재

  • 알고리즘 구현 방법

    - 최초, 모든 간선을 가중치에 따라 오름차순 정렬

    - 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴

    - 만약, 선택한 간선에 의해 사이클이 존재하면 다음으로 가중치가 낮은 간선을 선택

    - n-1개의 간선이 선택될 때까지 앞의 과정을 반복

4. 다익스트라(Dijkstra) 알고리즘

  • 최단 경로란 간선의 가중치가 있는 유향 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로

  • 단일 시작점 최단 경로 문제는 출발점에서 다른 모든 정점들에 이르는 최단 경로를 구하는 문제

    - 다익스트라 알고리즘과 벨만-포드(Bellman-Ford)알고리즘

  • 다익스트라 알고리즘은 음의 가중치를 허용하지 않지만 벨만-포드 알고리즘은 음의 가중치를 허용

  • 벨만 포드 알고리즘은 가중치의 합이 음인 사이클은 허용하지 않음

 

 

<Reference>

- https://swexpertacademy.com/main/main.do