그래프의 모든 정점들을 빠지지 않고 방문하는 것을 순회라고 한다.
순회할 때 정점을 한번 방문하면 두번 방문하면 안된다.
모든 정점들을 한번씩 빠짐없이 방문하는 것이 순회이고 깊이 우선탐색(DFS)와 너비 우선탐색(BFS)로 나뉘어지게 된다.
깊이 우선탐색(DFS)
DFS 방법은 스택이나 재귀 호출로 다음 방문할 정점을 얻는다.
같은 정점을 재방문 하는 것을 막기 위해(한번씩만 방문하기 위해) 불방문 배열을 사용한다
DFS 방법은 스택 자료구조가 필요한데, 스택은 한쪽 방향으로 PUSH와 POP이 이루어지는 자료구조이다.
먼저 그래프의 출발 정점을 하나 잡아준다.
트리의 경우 무조건 루트가 출발 정점이지만, 그래프는 어디에서나 출발할 수 있다. 따라서 어느 정점이나 모두 출발 정점이 될 수 있기 때문에 임의적으로 하나의 출발 정점을 잡아준다 (여기서는 0번으로 출발 정점을 잡는다)
출발 정점과 정점의 개수만큼 방문 배열 필요
순서 : 스택이 비어있는지 확인하고 꺼내면서 인접 정점을 PUSH 하는 것을 반복
- 출발 정점이 정해지면(예:0번) 스택이라는 자료구조에 출발 정점을 PUSH 해줍니다.
- 그 다음 스택이 비어있는지 확인합니다.
- 스택이 비어있지 않으면 POP을 해서 0번을 꺼냅니다 (비어 있지 않다면 꺼낸다)
- 꺼내면서 방문을 했다고 보고, 꺼내면서 방문을 하게 되면 출발 정점 0번과 인접한 1번, 2번, 3번 정점을 다시 한번 PUSH 해줍니다.
- 1번 PUSH, 2번 PUSH, 3번 PHSH를 한 뒤 스택이 비어있는지 물어봅니다
- 스택이 비어있지 않으니 아니라고 하면 LIFO에 의해 마지막에 들어온 3번이 나가게 됩니다. POP하면서 3번을 방문 체크 하게 되는 것이고, 3을 꺼내면서 3번과 인접한 0번 2번 5번을 다시 PUSH 합니다
- 0번 2번은 PUSH한 적이 있기 때문에 방문하지 않은 5번만 PUSH 합니다
- 스택이 비어있는지 물어보고 아니라면 다시 5번을 꺼내면서 5번과 인접한 정점들이 들어가게 됩니다. (3번 2번 4번 6번)
- 한번도 방문한 적 없는 4번, 6번이 PUSH가 되고 6번을 꺼내면서 6번과 인접한 5,7,8번 중 7,8번이 PUSH 됩니다
- 8번을 POP하면서 8번과 인접한 노드 중 방문하지않은 9번이 PUSH 됩니다
- 9번을 꺼내면서 9번과 인접한 정점은 모두 방문했기 때문에 그 다음 7번을 pop합니다. 7번 역시 인접한 정점이 모두 push한적이 있습니다
- 남은 모든 정점들도 모두 방문한 적이 있습니다
- 비어 있는지 물어보고, 스택이 텅텅 비어 있는 상태가 됩니다. 스택이 비어있다는 것은 모든 정점이 빠짐없이 방문 되었다는 소리이고 이 그래프의 순회를 마치게 됩니다.
- 0 → 3 → 5 → 6 → 8→ 9 이렇게 끝까지 따라갔다가 7 → 4 → 2 → 1 로 가는 순서로 모든 정점을 빠짐없이 한번씩 방문하였습니다.
* 탐색 결과는 유일한 결과 값이 아닙니다. 그래프 연결 상태에 따라 순회 방식은 달라질 수 있습니다
최소신장트리(MST)
신장트리란 그래프 내의 모든 정점을 포함하는 최소 연결 그래프, 부분 그래프이다.
그래프의 정점이 3개라면, 최소로 연결하기 위해 간선은 2개 필요하다.
정점이 4개라면 간선은 3개 필요하다. 즉, N개의 정점이 있다면 N-1개가 필요하게 된다.
N개의 정점을 N-1개의 간선으로 연결하는 순간 필연적으로 트리 자료구조를 만들 수 있게 된다.
사이클이 형성되면 안된다.
정점이 7개라면 간선은 6개
어떤 그래프에 대한 신장트리는 한개가 아닌 여러개가 존재 가능하다
모든 정점이 연결된 완전 그래프에서 만들 수 있는 신장트리의 개수는 N^(N-2)개를 만들 수 있다.
연결 되었을 때 최소한의 비용으로 연결되는 신장트리가 있는데,
간선의 비용 값을 최소한으로 연결한 트리를 최소신장트리(MST)라고 부르게 된다.
최소신장트리는 왜 만드는 걸까?
예를 들어, 상수도관이 있다면 모든 가구와 집에는 수돗물이 공급되어야 한다.
모든 집의 상수도관은 서로 연결되어야 하고 모든 정점을 포함하고 있어야 한다. 그래서 비용이 많이 들기보다는 최소의 비용으로 연결해주는게 좋다.
이런 트리구조에서 최소한의 비용인 애들부터 연결을 시켜서 MST로 만들면 최소 비용으로 연결을 시킬 수 있다.
크루스칼의 최소신장트리 알고리즘
- 항상 최선의 선택을 하는 그리디(탐욕) 알고리즘
- 비용이 가장 작은 것을 매 순간 선택한다
- 사이클이 형성되면 안된다
- 모든 비용을 일단 오름차순하여 정렬합니다
- 비용이 작은 애들부터 정렬을 시켜 연결을 시켜나갑니다.
- 2번과 3번의 비용이 2로 가장 낮기 때문에 2번과 3번을 먼저 연결시킵니다
- 그다음 2번 1번 / 4번 6번 / 0번 1번을 연결 시킵니다
- 0번 3번을 연결하려고 보니까 사이클이 형성이 되죠, 사이클이 형성되는 순간 최소 연결을 할 수 없습니다. 그러면 0번 3번은 연결하지 않습니다
- 1번 3번도 마찬가지 입니다
- 2번 4번은 연결해도 되니까 합니다. 그 다음 1번 5번을 연결해줍니다…
- 이렇게 우리가 최소한의 비용으로 트리를 만들 수 있게 되고, 이것을 우리는 MST라고 부르게 됩니다.
- 우리가 비용 오름차순을 해서 비용이 작은 정점부터 선택해서 만들었죠, 그러면 가장 좋아 보이는 순간을 매순간 선택해서 연결하고 연결해서 결과적으로 최소한의 비용으로 트리를 만듭니다.
- 즉 욕심쟁이 방법론, 그리디 알고리즘으로 문제를 해결하는 방식입니다 (매순간 최순간의 선택이 결국 최선의 선택)
0번 3번이 연결되어 사이클이 발생되는 것은 유니온 파인드 알고리즘으로 알 수 있습니다.
합집합 찾기, 서로소 집합인데 각 정점이 연결되어 있는지 아닌지를 알고 싶은 알고리즘 입니다.
다익스트라 알고리즘
- 최단 경로 탐색 알고리즘
- 0번 정점에서 각 정점까지의 최단 경로를 찾아 저장한다.
실제 구글 맵이나 자동차 네비게이션 등에서 경로를 탐색할 때 사용되며, 음수 가중치가 없기 때문에 실생활에서 사용하기 유용하다.
다익스트라 알고리즘은 하나의 출발 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다.
플로이드(floyed)알고리즘과 다익스트라 알고리즘의 차이점은,
하나의 출발 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘은 다익스트라 알고리즘이고 모든 정점에서 모든 정점까지의 최단 경로를 찾는 알고리즘은 플로이드 알고리즘이다.
다익스트라 알고리즘은 탐욕 알고리즘이면서 동적계획법 알고리즘이다.
하나의 출발 정점에서 다른 모든 정점까지 가는 최단 경로를 찾는 알고리즘이다. 출발 정점에서 시작해서 각각의 정점으로 가는 최단 경로를 찾는다
- 0번 정점에서 시작해서 0 → 1은 3이 됩니다
- 0번에서 시작해서 1번으로 가면 1이 됩니다
- 0번에서 3으로 가면 10이 됩니다
- 0번에서 4번으로 바로 가는 길은 없습니다
- 0번에서 5번으로 바로 가는 길은 없습니다
- 출발 정점 0에서 각각의 정점으로 가는 비용을 계산한 것인데요, 다익스트라 알고리즘은 여기서 최소비용, 최단 거리를 찾습니다
- 이 값보다 더 낮은 비용의 값이 있는지를 찾아냅니다. 가장 낮은 정점의 비용은 2번이죠, 0 → 2의 비용이 1이 들면 0→2→3은 9가 됩니다 (원래 0→3은 10이었는데 2를 거치니까 8이 됨)
- 0 → 4로 가는 비용이 없는데 최소 비용인 2를 거쳐서 가니까 0 → 2 → 4로 5의 값이 됩니다
- 0 → 5로 가는 비용이 없는데 0→2→5로 가면 7의 값이 됩니다
- 값을 갱신해줍니다
- 그 다음으로 낮은 비용은 0→1인 3입니다
- 0→1→3 으로 1번을 거쳐서 가면 원래 9였던 비용이 8이 됩니다.
- 이전에 있던 비용보다 8이라는 비용이 낮아 이 비용으로 갱신합니다
- 기존보다 많은 비용이 들면 기존의 값을 유지합니다
'컴퓨터 일반 > 자료구조론' 카테고리의 다른 글
| 자료구조 문제 정리 (1) 배열, 리스트 (4) | 2024.10.25 |
|---|---|
| 알고리즘 시간복잡도 (0) | 2024.10.24 |
| 선형 자료구조 (0) | 2024.10.24 |
| 자료구조 트리 (3) | 2024.10.23 |
| 자료구조 그래프 정리 (1) | 2024.10.23 |
