[자료구조] 그래프

• 그래프 
• 원소와 원소사이를 다:다 연결을 해 놓는 것
• 정점과 간선으로 구성되어있으며 (1. 이차원 배열 2. 연결 리스트) 로 구현할 수 있다.

 

• 탐색 방법
• 그래프의 모든 노드를 탐색하고 싶을 때 = 그래프 순회 / 그래프 탐색이라고 한다
1. DFS (깊이 우선 탐색) : Stack으로 구현
2. BFS (넓이 우선 탐색) : Queue로 구현

 

• 신장 트리
• 정점이 n개 일때 n-1개의 간선을 가지는 트리 형태
• DFS / BFS를 구하면 신장트리가 나옴 

+) 트리와 그래프의 차이? 트리는 그래프의 일부분으로 Cycle이 없는 그래프를 의미

 

• 최소 비용 신장 트리
• 만약 간선들이 모두 가중치를 가지고 있다면? 신장트리를 만들때 어떻게 최소비용으로 만들 수 있을까?

 

1. 크루스칼 알고리즘
• 간선들 사이의 가중치를 정렬한 후 정점들 사이에 높은 가중치가 있는 간선들을 삭제하거나 가장 낮은 간선들을 삽입하면서 최소 비용 신장 트리를 만드는 방법
• 삽입 방법
1. 간선을 가중치가 낮은 순으로 정렬한다. (ASC)
2. 정점들에 낮은 가중치를 가진 간선들을 연결해가며 그래프를 완성한다.
3. 단 Cycle이 생기면 해당 간선을 삭제한 후 다음 가중치를 가진 간선으로 넘어간다.
• 삭제 방법
1. 간선을 가중치가 높은 순으로 정렬한다.(DESC)
2. 정점에 높은 가중치를 가진 간선들을 삭제해가며 그래프를 완성한다.
3. 단 간선이 한 개도 없는 노드가 생기면 해당 다음 가중치를 가진 간선으로 넘어간다. 

 

1. 프림 알고리즘
• 간선들을 가중치에 따라 정렬하지 않고 해당 노드에서 가중치가 낮은 간선들을 찾아나가는 방법
1. 시작 노드에서 가중치가 낮은 간선을 따라 다음 노드를 설정한다.
2. 현재 노드와 이전 노드에 연결된 모든 간선들 중 가중치가 가장 낮은 간선을 선택하여 다음 노드를 선택한다.
3. 단 Cycle이 생기면 해당 간선을 제외하고 그래프를 생성한다.

 

• 최단 거리 알고리즘
• 가중치 그래프에서 시작 노드에서 종료 노드까지 갈 수 있는 최소 비용

 

1. 다익스트라 알고리즘
• 시작 노드에서 목적 노드로 최소 비용으로 갈 수 있는 경로를 구하는 알고리즘
1. 시작 노드에서 연결된 간선들의 가중치를 1차원 배열에 적는다. 단 시작 노드에 연결되어있지 않는 노드들은 무한대로 정의한다.
2. 그 중 가중치가 가장 낮은 간선이 연결된 노드를 다음 노드로 선택한다.
3. 이미 방문한 노드를 제외한 현재 노드에 연결된 간선들의 가중치를 배열에 적는다. 단 이미 가중치가 적힌 노드가 있다면 “현재 노드를 거쳐서 해당 노드로 가는 비용”과 “적혀있는 비용”를 비교하여 더 낮은 가중치의 값을 기록한다.

  > 예를 들어 array[B] = min(array[B], array[A] + A노드에서 B노드로 가는 간선 가중치)

1. 방문하지 않은 노드들 중 현재 가중치가 가장 낮게 기록된 노드를 다음 노드로 선택한다.
2. 시작 노드에서 각 노드로 갈 수 있는 최소 비용들이 적힌 1차원 배열이 결과로 나오게 된다

 

1. 플로이드 최단 경로 알고리즘
• 모든 정점 사이의 최단 경로를 구할 수 있는 알고리즘
1. 2차원 배열에 모든 노드들에 연결된 간선들의 가중치를 적는다. 단 한번에 갈 수 없는 노드 사이의 거리는 무한대로 정의한다.
2. 현재 노드와 연결된 간선들 + 자기 자신으로 가는 간선의 가중치 를 제외하고 해당 노드를 거쳐간 값을 계산한 가중치와 현재 기록된 가중치를 비교하여 더 낮은 가중치를 적는다.

     > 현재 노드가 A 라면 array[A][A] 와 array[A][B] 등 A와 관련된 간선을 제외한 모든 배열 값에 아래와 같은 식을 적용한다.
          ex) B에서 D로 가는 최단 거리가 적힌 배열 업데이트 : array[B][D] = min(array[B][D] // 원래 비용, array[B][A] + array[A][D] // B와 D를 갈 때 A를 거쳐가는 비용)

1. 결과 값으로 해당 노드에서 다른 노드로 갈 수 있는 최단 거리가 있는 2차 배열이 생성된다.