위상 정렬 알고리즘 (Topology Sort)

위상 정렬 알고리즘 : 순서가 정해져 있는 작업을 순차적으로 탐색하는 알고리즘

                            

 

 

위와 같은 그래프가 주어졌을 때 화살표는 작업의 순서를 나타낸다. 

ex) 1이 끝나면 3을 시작할 수 있다.

ex) 2와 3이 끝나면 5를 시작할 수 있다.

 

<위상정렬 알고리즘>

단순하게 자신으로 들어오는 indegree가 모두 제거되면 자신의 일을 시작하면 된다.

 

 

<전체 코드>

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

vector<int> a[10];
int indegree[10];
int n = 7;

void topology()
{
	queue <int> q;
	for (int i = 1; i <= n; i++)
	{
		if (indegree[i] == 0)q.push(i); // 자신 전에 선행되어야 할 일이없다면 큐에 저장
	}

	for (int i = 0; i < n; i++)
	{
		if (q.empty())  //n개 모두 탐색하기 전에 탐색이 끝나면 사이클 존재.
		{
			cout << "사이클이 발생하였습니다." << "\n";
			return;
		}

		int node = q.front();
		q.pop();

		cout << node << " ";
		for (int i = 0; i < a[node].size(); i++)
		{
			int next = a[node][i];
			indegree[next]--;
			if (indegree[next] == 0)q.push(next);
		}
	}
}

int main()
{
	a[1].push_back(2);  //노드 1에서 노드 2로가는 길
	indegree[2]++;   //노드 2의 indegree 증가
	a[1].push_back(3);
	indegree[3]++;
	a[1].push_back(4);
	indegree[4]++;
	a[2].push_back(5);
	indegree[5]++;
	a[3].push_back(5);
	indegree[5]++;
	a[3].push_back(6);
	indegree[6]++;
	a[5].push_back(7);
	indegree[7]++;
	a[6].push_back(2);
	indegree[2]++;

	cout << " 탐색 순서 : ";
	topology();

	return 0;
}

 

 

 

같은 위상끼리는 코딩 방식에 따라 얼마든지 순서가 달라질 수 있다.

 

 

 

<위상정렬 관련 기본 문제>

1. 백준 1005번: ACM Craft   :  wlshddlek.tistory.com/40?category=888059

2. 백준 1766번: 문제집  :  wlshddlek.tistory.com/41?category=888059

 

 

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.