22_4_DAG.md

22.4 Topological Sort

Directed acyclic graph

https://www.acmicpc.net/problem/2252

책안의 구조

DFS 사용 Cormen et al. (2001); Tarjan (1976)이 제안

std::stack<int> topologicalsort(const Graph& G)
{
	const int n = G.size();
	std::vector<bool> visit(n, false);
	stack<int> S; // 실제 정렬된값이 역순으로 들어가있다.
	for (std::size_t i = 1; i < n; i++)
	{
		if (visit[i] != true)
		{
			DFS_TS(G, visit, S, i);
		}
	}
	return S;
}

//recursion
void DFS_TS(const Graph& G, std::vector<bool>& visit,
	stack<int>& S, int x)
{
	visit[x] = true;
	//std::cout << x << ' '; // 순회출력
	for(int next : G[x])
	{
		if (visit[next] != true)
		{
			DFS_TS(G, visit, S, next);
		}
	}
	S.push(x);
}

//for with stack
void DFS_TS(Graph& G, std::vector<bool>& visit,
	stack<int>& S, int x)
{
	visit[x] = true;

	std::stack<int> sub_s;
	sub_s.push(x);

	//std::cout << sub_s.top() << ' '; // 순회출력

	while (!sub_s.empty())
	{
		int y = sub_s.top();
		for (std::size_t i = 0; i < G[y].size(); i++)
		{
			int next = G[y][i];
			if (visit[next] != true)
			{
				visit[next] = true;
				sub_s.push(next);
				//std::cout << sub_s.top() << ' '; // 순회출력
				i = -1;
				y = sub_s.top();
			}

		}
		S.push(sub_s.top());
		sub_s.pop();
	}
}

함수 스택이 가장 빠르다.

기존 DFS와 차이는 마지막 sub_s.pop()하기전에 값을 S에 넣는 것이다.

해당 알고리즘의 개선은 다음의 코드들을 참고.

https://www.acmicpc.net/source/14181460

https://www.acmicpc.net/source/14181554

https://www.acmicpc.net/source/14181784

재귀 https://www.acmicpc.net/source/14192056

반복 https://www.acmicpc.net/source/14193108

Kahn's algorithm

참고 : https://blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221236874984&proxyReferer=https%3A%2F%2Fwww.google.com%2F

https://www.geeksforgeeks.org/topological-sorting-indegree-based-solution/

std::vector<int> topologicalsort(const Graph &G, int v)
{
	std::vector<int> indegree(v + 1);
	std::queue<int> qu;
	std::vector<int > DAG;
	for (int i = 1; i <= v; i++)
	{
		for(int j : G[i])
		{
			indegree[j]++;
		}
	}

	for (int i = 1; i <= v; i++)
	{
		if (indegree[i] == 0)
		{
			qu.push(i);
		}
	}
	for (int i = 1; i <= v; i++)
	{
		if (qu.empty())
		{
			return DAG;
		}
		int x = qu.front();
		qu.pop();
		DAG.push_back(x);

		for(int y : G[x])
		{
			indegree[y]--;
			if (indegree[y] == 0)
			{
				qu.push(y);
			}
		}
	}
	return DAG;
}