*그래프의 첫 단원에는 대개 쾨니히스베르크의 다리라고 해서, 7개의 다리를 한 번씩만 건너서 모든 섬을 찍는 법은? 같은 인트로로 시작한다.
*그러나 수학자 오일러는 그런 방법이 없다고 단언했다. 왜 그랬을까?
*한붓그리기는 연결되어 있는 선이 홀수개인 점이 아예 없거나, 두개만 있는 도형에서만 가능하다.
*그래프란 정점의 집합을 V, 간선의 집합을 E, 그리고 그래프를 G라고 했을때 G = (V,E)이다.
*간선으로 연결된 두 점을 인접(adjacent)하다고 표현한다.
*사이클(cycle)이란 어느 한 정점을 두 번 이상 거치도록 되어 있는 경우이다.
*정점 사이의 인접 관계를 나타내는 방법은 인접행렬과 인접리스트, 두 가지 방법이 있다.
*인접행렬은 정점의 개수X정점의 개수의 행렬을 만들어 두 정점이 인접한 경우 1로 표현한다. ->무방향 그래프일 경우 대칭을 이룬다.
*인접리스트는 모든 정점에 대해 인접한 정점을 연결리스트로 연결한 형태의 자료구조이다.
그래프 순회
깊이 우선 탐색(Depth first Search,DFS)
-더 나아갈 길이 보이지 않을 때 까지 깊이 들어간다.
-길이 나오지 않을 때 까지 그래프이 정점을 타고 싶이 들어가다가 더 이상 방문해왔던 정점 말고는 다른 이웃을 갖고 있지 않은 정점을 만나면 뒤로 돌아와 다른 경로로 뻗어 있는 정점을 타고 방문을 재개하는 방식이다.
-구현 방식을 보면 알겠지만 스택과 방문여부를 저장하는 배열로 구현한다.
-방문했던 정점을 스택에 계속 push하다가, 막힌 정점이 나오면 더 새로운 인접 정점이 나올 떄 까지 pop하는 방식이다.
-코드를 살펴보자.
void DFS (Vertex *vertex){
Edge *edge = NULL;
printf("%d" , vertex->Data);
vertex->visited = Visited;
edge = vertex->AdjacencyList;
while(edge != NULL){
if(edge ->Target != NULL && E->Target->visied == NotVisited)
DFS( edge->Target);
edge = edge->Next;
}
}너비우선탐색(Breadth First Search)
시작정점을 지나고 나면 깊이가 1인 모든 정점을 방문하고, 그 다음에는 깊이가 2인 모든 정점을 방문한다. 이런식으로 한 단계식 깊이를 더해가며 해당 깊이에 있는 모든 정점들을 방문한다. 탐색과정은 다음과 같다.
1.시작 정점을 "방문했음"으로 표시하고 큐에 삽입한다.
2.큐로부터 정점을 제거한다. 제거한 정점이 이웃하고 있는 인접 정점 중 아직 방문하지 않은 곳들을 '방문했음'으로 표시하고 큐에 삽입한다.
3.큐가 비어있게 되면 탐색이 끝난 것이다. 큐가 빌 때 까지 2번 과정을 반복한다.
void BFS(Vertext* vertex , LinkedQueue *queue){
Edge* edge = NULL;
printf("%d" , vertex->data);
vertex->visited = Visited;
LQ_Enqueue(&queue , LQ_CreateNode(V)); //방문 했으므로 첫 시작 정점을 큐에 삽입한다.
while (!LQ_IsEmpty(queue)){
Node* popped = LQ_Dequeue(&Queue);
vertex = popped->data;
edge = vertex->AdjacencyList;
while( edge != NULL ){ /* 큐에서 꺼낸 정점의 인접 정점을 조사한다. */
vertex = edge->target;
if(vertex != NULL && vertex->visited == NotVisited){
printf("%d" , vertex->data);
vertex->visited = Visited;
LQ_Enqueue(&queue, LQ_CreateNode(V));
}
edge = edge->next;
}
}
}위상정렬
*위상이란 어떤 사물이 다른 사물(정점)과의 관계 속에서 가지는 위치나 상태를 말한다.
*이 위치의 속성은 간선의 방향에 의해 결정된다.
*위상정렬을 하기 위해서는 그래프에 방향성이 있어야 하며, 싸이클이 없어야 한다.
*위상정렬의 과정을 살펴보자.
1.리스트를 준비한다.
2.그래프에서 진입 간선이 없는 정점을 리스트에 추가하고, 해당 정점 자신과 진출 간선을 제거한다.
3.모든 정점에 대해 2를 반복하고, 정점이 없을때 까지 반복한다.
4.이때의 리스트가 위상정렬된 그래프이다.
->이 방식과 똑같이 위상정렬을 수행하면서 조금 더 '우아한'방법은 깊이우선탐색을 이용하는 것이다.
1.리스트를 준비한다.
2.그래프에서 진입간선이 없는 정점에 대해 깊이우선탐색을 시행하고, 탐색 중에서 더 이상 옮겨갈 수 있는 인접 겅점이 없는 정점을 만나면, 이 정점을 리스트의 새로운 헤드로 입력한다.(첫번째 인덱스에 삽입한다는 뜻이다.)
3. 2를 정점이 없을때 까지 반복한다.
최소신장트리(Minimum Spanning Tree)
*간선에 가중치(weight)가 생긴다.
*여기서 사용되는 신장(spanning)의미는 그래프이ㅡ 모든 정점을 연결한다는 뜻이다.
*즉 가중치의 합이 최소가 되는 신장 트리이다.
*최소한의 비용으로 모든 도시를 연결하는 도로를 건설할 방법을 찾아라 같은 문제에 적용하기 아주 좋다.
*프림 알고리즘과 크루스칼 알고리즘, 두 가지가 있다.
프림 알고리즘
1.그래프와 최소 신장 트리를 준비한다. 이때 최소 신장 트리는 노드가 하나도 없는 상태이다.
2.그래프의 임의의 정점을 시작 정점을 선택하여, 최소 신장 트리의 루트 노드로 삽입한다.
3.최소 신장 트리에 삽입되어 있는 정점들과 이 정점들의 모든 인접 정점 사이에 있는 간선의 가중치를 조사한다. 이들 중, 가장 가중치가 작은 간선을 골라 해당 인접정점을 최소 신장 트리에 삽입한다. (당연히 삽입하면서 사이클을 형성해서는 안된다.)
4.그래프의 모든 정점을 입력할 때 까지 3번 과정을 반복한다.
(그림 생략)
*책에 따르면 프림 알고리즘은 두 가지 문제를 지닌다.
첫번째는 최소 신장 트리의 자료구조로 무엇을 사용할 것인가에 대한 것이다. 보통 최소 신장 트리는 그래프이므로, 그래프로 구현한다.
두번재는 조사 대상 간선에서 최소 가중치를 가진 녀석을 골라내는 과정에서 발생하는 성능이다. 최소 신장 트리에 정점이 추가될 때 마다 그래프의 모든 정점을 순회하면서 이 정점들이 최소 신장 트리에 추가되었는지 확인하고, 최소 신장 트리에 추가되어 있는 모든 정점들의 간선을 조사해서 최소 가중치를 찾아야 한다.
그래프의 정점이 n개라면, 최소 신장 트리에 n번만큼 정점을 추가해야 하고, 정점을 추가할 때 마다 n번 순회하므로, n^2회 반복을 돌아야 한다.
이 문제는 삽입과 삭제가 빠르고, 최소 값을 찾는데 거의 비용이 들지 않는 우선순위 큐를 이용하는게 바람직 하다. 코드를 보자.(코드가 넘 길어서 생략)
크루스칼 알고리즘
그래프 내의 모든 간선들의 가중치 정보를 사전에 파아갛고, 이 정보를 토대로 최소 신장 트리를 구축해 나간다.
1.그래프 내의 모든 간선을 가중치의 오름차순으로 목록을 만든다.
2.목록을 차례로 순회하면서 간선을 최소 신장 트리에 추가한다. (당연히 싸이클이 형성되면 안된다.)
*크루스칼 알고리즘의 핵심은 얼마나 효율적으로 '사이클'을 찾아내는가에 있다.
*DFS를 생각해 볼 수 있는데, 비용이 크다. 분리집합을 고려해보자.
*각 장점에 대해서 집합을 가지고 있고, 간선으로 연결된 경우 합집합을 수행한다. (이때 간선으로 연결할 두 정점이 같은 집합에 속해 있다면 사이클이다)
*따라서 간선으로 이을 두 정점이 같은 집합에 소속되어 있는지의 여부만 확인하면 된다.
*동작과정은 다른 블로그를 참조한다.
최단 경로 탐색
*그래프에서 최단경로탐색 문제는 한 정점에서 다른 정점으로 이동할 때 가중치 합이 최소값이 되게 만드는 경로를 찾는 알고리즘이다.
*다익스트라가 고안한 다익스트라 알고리즘을 살펴보자.
다익스트라 알고리즘
*프림 알고리즘이 간선의 길이를 이용하여 어떤 간선을 먼저 연결할지 결정하는 반면, 다익스트라는 '경로의 길이'를 감안하여 간선을 연결한다는 점이 차이가 있다.
*전제조건은 싸이클이 없는 방향성 그래프에서만 사용할 수 있다.
1.각 정점 위에 시작점으로부터 자신에게 이르는 경로의 길이를 저장할 곳을 준비하고 모든 정점 위에 있는 경로의 길이를 무한대로 초기화 한다.
2.시작 정점의 경로 길이를 0으로 초기화하고 최단 경로에 추가한다.
3.최단 경로에 새로 추가된 정점의 인접 정점들에 대한 경로 길이를 갱신하고 이들을 최단 경로에 추가한다. 만약 추가하려는 인접 정점이 이미 최단 경로 안에 존재한다면 갱신되기 이전의 경로 길이가 새로운 경로의 길이보다 더 큰 경우에 한해 다른 선행 정점을 지나던 기존 경로를 현재 정점을 경유하도록 수정한다.
4.그래프 내의 모든 정점이 최단 경로에 소속될 때 까지 3번의 과정을 반복한다.