위상정렬 (Topological Sort) - Indegree

1. 소스 코드

http://www.playsw.or.kr/repo/cast/110 그림을 참조하여 위상정렬을 해 보았다.

상세 알고리즘 동작은 위 블로그를 참조함.

#include <iostream> #include <string> #include <vector> #include <queue> const std::string str[] = { "컴퓨터공학입문", "논리회로", "자료구조", "어셈블러", "데이터베이스", "시스템프로그램밍", "컴퓨터구조", "알고리즘", "네트워크", "운영체제" }; const int N = 10; int M; std::vector<int> G[N]; std::queue<int> Q; std::queue<int> R; int in[N]; struct edge_t { int from; int to; }; int getIndex(const std::string s) { int sz = sizeof(str)/sizeof(str[0]); for(int i = 0; i < sz; i++) { if(s == str[i]) { return i; } } return -1; } edge_t data[] = { {getIndex("컴퓨터공학입문"), getIndex("자료구조")}, {getIndex("논리회로"), getIndex("컴퓨터구조")}, {getIndex("자료구조"), getIndex("데이터베이스")}, {getIndex("자료구조"), getIndex("알고리즘")}, {getIndex("자료구조"), getIndex("시스템프로그램밍")}, {getIndex("어셈블러"), getIndex("시스템프로그램밍")}, {getIndex("어셈블러"), getIndex("컴퓨터구조")}, {getIndex("시스템프로그램밍"), getIndex("네트워크")}, {getIndex("시스템프로그램밍"), getIndex("운영체제")}, }; void insertData() { M = sizeof(data)/sizeof(data[0]); for(int i = 0; i < M; i++) { int from = data[i].from; int to = data[i].to; G[from].emplace_back(to); in[to]++; } } void printIndegree() { for(int i = 0; i < N; i++) { std::printf("%-25s : %d\n", str[i].c_str(), in[i]); } } void printGraph() { for(int i = 0; i < N; i++) { std::printf("%-25s ", str[i].c_str()); for(auto e : G[i]) { std::printf("-> %s", str[e].c_str()); } std::cout << std::endl; } } int main() { insertData(); //printGraph(); //printIndegree(); for(int i = 0; i < N; i++) { if(in[i] == 0) { Q.push(i); in[i] = -1; } } while(Q.empty() == false) { int qf = Q.front(); Q.pop(); R.push(qf); for(auto e : G[qf]) { in[e]--; } for(int i = 0; i < N; i++) { if(in[i] == 0) { Q.push(i); in[i] = -1; } } } while(R.empty() == false) { std::printf("%s ", str[R.front()].c_str()); R.pop(); } std::cout << std::endl; return 0; }

2. 실행 결과

컴퓨터공학입문 논리회로 어셈블러 자료구조 컴퓨터구조 데이터베이스 시스템프로그램밍 알고리즘 네트워크 운영체제