[알고리즘] ch 7. 그래프 (2) - 위상 정렬

7.4 위상 정렬

 

위상 정렬 (Topological Sort)

- 위상 = 어떤 정점이 다른 정점과의 관계 속에서 가지는 위치 

- 그래프 내 서로 인접한 정점 사이의 관계에 '위치'라는 속성이 존재한다는 뜻

- 위치는 간선 방향에 의해 결정

- 간선을 뻗어내는 정점이 앞이 되고, 간선을 받아들이는 정점이 뒤가 됨 

- 이 앞/뒤 관계를 정렬하는 작업이 위상정렬

- '순서가 정해져 있는 작업'을 차례로 수행해야할때 그 순서를 결정해주기 위해 사용하는 알고리즘

 

- 위상을 정렬하려면 1) 그래프에 방향성이 있어야 하며 2) 그래프 내에 사이클이 없어야 함

 -> DAG(Directed Acyclic Graph)

 

 

7.4.1 위상 정렬의 동작 방식

 

- 간선은 정점과 정점 사이의 관계를 설명하는 역할 수행

 

- 두 정점이 이웃 또는 인접 관계에 있다는 사실뿐 아니라 간선이 방향성을 가진 경우 어느 정점이 선이고 어느 정점이 후인지도 설명

- 진입 간선(Incoming Edge) = 정점으로 들어가는 간선

- 진출 간선(Outgoing Edge) = 정점에서 나가는 간선

 

 

 

위상 정렬 알고리즘 

 

 1) 리스트를 하나 준비 

 

 2) 그래프에서 진입 간선이 없는 정점을 리스트에 추가하고 해당 정점 자신과 진출 간선을 제거 

 

 3) 모든 정점에 대해 단계 2)를 반복하고 그래프 내에 정점이 남아 있지 않으면 정렬을 종료 . 이떄 리스트에는 위상 정렬된 그래프가 저장됨

 

ex)

 

- 진입 간선이 없는 정점은 A와 B 2개가 있으며, B를 리스트에 추가하고 B와 진출 간선을 모두 제거 

 

- B를 제거하니 진입 간선이 없는 정점으로 A와 E가 남음

- E를 리스트에 추가하고 E와 진출 간선을 제거 

 

- 진입 간선이 없는 정점이 A 하나 뿐이므로 A를 리스트에 추가하고 A와 진출 간선을 모두 제거 

 

- 이번에는 C와 D가 제거 대상 후보

- D를 리스트에 추가하고 진출 간선을 제거 

 

- 진입 간선이 없는 C와 G 중에서 G를 리스트에 추가하고 G와 진출 간선을 함께 제거 

 

- 제거 대상 후보가 C 하나 . C를 리스트에 추가하고 진출 간선과 함께 제거

- F를 리스트에 추가하고 해당 정점과 진출 간선을 제거 

 

- 마지막으로 남은 정점 H를 리스트에 추가 

- 완성된 리스트가 바로 그래프를 위상정렬한 결과 

 

 

깊이 우선 탐색을 이용한 위상정렬 알고리즘

 

 1) 리스트를 하나 준비

 

 2) 그래프에서 진입 간선이 없는 정점에 대하여 깊이 우선 탐색을 시행하고, 탐색 중에 더 이상 옮겨갈 수 있는 인접 정점을 만나면 이 정점을 리스트에 새로운 '헤드'로 입력 

 

3) 단계 2)를 반복하다가 더 이상 방문할 정점이 없으면 깊이 우선 탐색을 종료. 깊이 우선 탐색이 끝나면 리스트에 위상 정렬된 그래프가 남음

 

ex)

- 리스트를 하나 준비한 다음. 진입 간선이 없는 정점을 찾아 깊이 우선 탐색을 시작

- 진입 간선이 없는 정점은 A와 B가 있고, A에서부터 시작

- A-C-F-H를 타고 그래프 안쪽으로 탐색하면 H를 만남 

- H에서 옮겨질 수 있는 인접 정점이 더 이상 없으므로 H를 리스트의 '헤드'로 삽입

 

- H에서 뒤로 돌아오면 정점 F를 만남. F의 유일한 인접 정점이 H였는데, H는 앞에서 방문했으니 현재는 더 방문할 정점이 없음 . F를 리스트의 헤드로 삽입하고 뒤로 돌아감

 

- 정점 C의 유일한 인접 정점은 F였는데 이미 방문했으므로 지금은 인접 정점이 없음

- C를 리스트의 헤드로 추가하고 뒤로 돌아감

 

- 정점 A의 인접 정점은 C와 D 2개. C는 이미 방문했고 D는 방문하지 않앗으므로 D를 타고 그래프 깊숙이 들어감 

- D를 거쳐 G에 도착하면 G의 유일한 인접 정점이었던 H가 이미 방문한 상태임

- G를 리스트에 헤드로 추가하고 뒤로 돌아감 

 

- D 역시 남은 인접 정점이 없음

- D를 리스트의 헤드로 삽입

 

- 다시 A로 돌아옴. A도 방문할 인접 정점이 더 이상 없으므로 A를 리스트의 헤드로 삽입 

 

- B를 타고 그래프 안으로 들어감

- B의 인접 정점 C와 E중 C는 이미 방문한 상태이므로 E를 방문하면 됨

- E는 인접 정점이 없는 상태이므로 E를 리스트의 헤드로 삽입하고 뒤로 돌아감

 

- B 하나만 남은 상태. 더 이상 방문할 수 있는 인접 정점이 없으므로 리스트의 헤드로 삽입

- 이렇게 깊이 우선 탐색도 끝났고 위상 정렬도 끝남 

 

위상정렬 함수 / DFS를 이용한 위상 정렬 함수 

 

//위상 정렬 
void TopologicalSort(Vertex* V, Node** List)
{
	while (V != NULL && V->Visited == NotVisited)
	{
		TS_DFS(V, List);
		V = V->Next;
	}
}

//DFS를 이용한 위상 정렬 
void TS_DFS(Vertex* V, Node** List)
{
	Node* NewHead = NULL;
	Edge* E = NULL;

	V->Visited = Visited;

	E = V->AdjacencyList;

	while (E != NULL)
	{
		if (E->Target != NULL && E->Target->Visited == NotVisited)
			TS_DFS(E->Target, List);

		E = E->Next;
	}

	printf("%c\n", V->Data);

	NewHead = SLL_CreateNode(V);
	SSL_InsertNewHead(List, NewHead);
}