반응형
위상 정렬 (Topological Sorting)
위상 정렬은 유향 비순환 그래프(DAG, Directed Acyclic Graph)의 정점을 순서대로 나열하는 방법입니다. 이 순서는 모든 간선 (u, v)에 대해 정점 u가 정점 v보다 먼저 나오는 순서를 의미합니다. 위상 정렬은 주로 작업 스케줄링, 컴파일러에서의 심볼 테이블 생성 등에 사용됩니다.
위상 정렬의 주요 특징
- DAG: 위상 정렬은 반드시 유향 비순환 그래프에서만 가능합니다.
- 순서: 정점 u에서 정점 v로 가는 모든 경로에 대해 정점 u는 정점 v보다 먼저 나옵니다.
위상 정렬의 구현 방법
- Kahn's Algorithm: 진입 차수를 이용한 위상 정렬
- DFS 기반 알고리즘: 깊이 우선 탐색을 이용한 위상 정렬
Kahn's Algorithm
Kahn's Algorithm은 진입 차수를 이용하여 위상 정렬을 수행하는 알고리즘입니다.
Kahn's Algorithm의 시간 복잡도:
- (O(V + E)), 여기서 (V)는 정점의 수, (E)는 간선의 수입니다.
Kahn's Algorithm 구현
#include <iostream>
#include <vector>
#include <queue>
// 그래프 클래스 정의
class Graph {
public:
Graph(int vertices);
void addEdge(int u, int v); // 간선 추가
void topologicalSort(); // 위상 정렬 호출
private:
int vertices; // 정점의 수
std::vector<std::vector<int>> adjList; // 인접 리스트
};
// 그래프 생성자 정의
Graph::Graph(int vertices) {
this->vertices = vertices;
adjList.resize(vertices);
}
// 간선 추가 함수 정의
void Graph::addEdge(int u, int v) {
adjList[u].push_back(v);
}
// 위상 정렬 함수 정의
void Graph::topologicalSort() {
std::vector<int> inDegree(vertices, 0);
// 모든 정점의 진입 차수를 계산
for (int u = 0; u < vertices; ++u) {
for (int v : adjList[u]) {
inDegree[v]++;
}
}
std::queue<int> q;
// 진입 차수가 0인 정점을 큐에 추가
for (int i = 0; i < vertices; ++i) {
if (inDegree[i] == 0) {
q.push(i);
}
}
int count = 0;
std::vector<int> topOrder;
while (!q.empty()) {
int u = q.front();
q.pop();
topOrder.push_back(u);
// 인접한 모든 정점의 진입 차수를 감소
for (int v : adjList[u]) {
if (--inDegree[v] == 0) {
q.push(v);
}
}
count++;
}
if (count != vertices) {
std::cout << "그래프에 사이클이 존재합니다." << std::endl;
return;
}
std::cout << "위상 정렬 결과:" << std::endl;
for (int i : topOrder) {
std::cout << i << " ";
}
std::cout << std::endl;
}
// 메인 함수
int main() {
Graph g(6);
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);
g.topologicalSort();
return 0;
}
DFS 기반 알고리즘
DFS 기반 알고리즘은 깊이 우선 탐색을 이용하여 위상 정렬을 수행하는 알고리즘입니다. 이 방법은 재귀를 사용하여 정점의 방문을 완료한 후 스택에 저장하는 방식으로 구현됩니다.
DFS 기반 알고리즘의 시간 복잡도:
- (O(V + E)), 여기서 (V)는 정점의 수, (E)는 간선의 수입니다.
DFS 기반 알고리즘 구현
#include <iostream>
#include <vector>
#include <stack>
// 그래프 클래스 정의
class Graph {
public:
Graph(int vertices);
void addEdge(int u, int v); // 간선 추가
void topologicalSort(); // 위상 정렬 호출
private:
int vertices; // 정점의 수
std::vector<std::vector<int>> adjList; // 인접 리스트
void topologicalSortUtil(int v, std::vector<bool>& visited, std::stack<int>& Stack); // 재귀 함수
};
// 그래프 생성자 정의
Graph::Graph(int vertices) {
this->vertices = vertices;
adjList.resize(vertices);
}
// 간선 추가 함수 정의
void Graph::addEdge(int u, int v) {
adjList[u].push_back(v);
}
// 위상 정렬 보조 함수 정의 (DFS 기반)
void Graph::topologicalSortUtil(int v, std::vector<bool>& visited, std::stack<int>& Stack) {
visited[v] = true;
for (int i : adjList[v]) {
if (!visited[i]) {
topologicalSortUtil(i, visited, Stack);
}
}
Stack.push(v);
}
// 위상 정렬 함수 정의
void Graph::topologicalSort() {
std::stack<int> Stack;
std::vector<bool> visited(vertices, false);
for (int i = 0; i < vertices; ++i) {
if (!visited[i]) {
topologicalSortUtil(i, visited, Stack);
}
}
std::cout << "위상 정렬 결과:" << std::endl;
while (!Stack.empty()) {
std::cout << Stack.top() << " ";
Stack.pop();
}
std::cout << std::endl;
}
// 메인 함수
int main() {
Graph g(6);
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);
g.topologicalSort();
return 0;
}
설명
- Kahn's Algorithm:
- 진입 차수를 계산하여 진입 차수가 0인 정점을 큐에 추가합니다.
- 큐에서 정점을 하나씩 꺼내어 인접한 정점의 진입 차수를 감소시킵니다.
- 모든 정점을 처리할 때까지 반복합니다. 사이클이 존재하는 경우를 감지할 수 있습니다.
- DFS 기반 알고리즘:
- 깊이 우선 탐색을 이용하여 정점을 방문합니다.
- 모든 인접한 정점을 방문한 후 현재 정점을 스택에 저장합니다.
- 모든 정점을 방문할 때까지 반복합니다.
- 스택에서 정점을 꺼내어 위상 정렬 결과를 출력합니다.
위상 정렬의 두 가지 구현 방법인 Kahn's Algorithm과 DFS 기반 알고리즘의 개념과 구현 방법을 이해했습니다. 질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 11: 강한 연결 요소 (Kosaraju, Tarjan 알고리즘)"에 대해 학습하겠습니다.
반응형