このポスターは羅東彬の25.位相位置合わせを参考に書かれています.

[コンセプト]

位相ソートとは、「守らなければならない順序」に従ってソートする方法です.例えば、夕食に料理の材料を買う過程をグラフで表す.

スーパーに行かないと物を選ぶこともできないし、従業員にカードを打つこともできません.また、選ばないと買えないし、同じようにお金を出さないと買えない.守らなければならない順番があるときは、どんな順番で処理すべきかを教えてくれます.これが位相合わせです.
次の同じ特徴を持つグラフを見てみましょう.

最終的な7番ノードにアクセスするには,どのような順序でノードを通過すべきか,位相ソートで表すことができる.この場合、グラフは「方向性のある非ループグラフ」であるべきであることに注意してください.
位相位置合わせでは、次の手順を繰り返します.筆者はキューを用いて位相整列を実現した.

を選択して、幹線数0のノードに入り、キューを挿入します.

キューからノードを取り出し、ノードに接続されているすべての幹線を削除します.

・プロセス

この手順を上記の例示的なグラフに適用すると、最初に幹線に進入したノードは存在しない1のみであり、1がキューに入れられる.次に、ノードをキューから取り出し、ノードに接続された幹線、すなわち1に接続された2と5に進入した幹線を削除する.2および5は、1からの進入幹線を除き、他の進入幹線がないため、進入幹線数は0である.したがって、2および5がキューに挿入される.その後2は列から退出し、幹線を外すと3列に挿入される.
その後、特殊な状況が発生し、5をキューから取り出した後、5に接続されているすべての幹線を削除し、幹線数0に入る新しいノードも現れない.5が指すノード6には、ノード4から進入する別の幹線が存在するからである.したがって、ノード4は、キューに挿入される条件が満たされないため、省略され、再びキューから取り出される.4からすべての幹線を取り出した後、6が幹線に入る数は0です.その後、6、7の順にアクセスし、ターゲットの7番ノードに到達するために、順序1 2 5 3 4 6 7が完了する.
以下に示すように、ソースコードとして表示します.

[ソースコード]

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

int n, k;

std::queue<int> q;

std::vector<int> adjacency[1001];	// 특정 노드가 가리키는 노드들의 집합 변수
int inDegree[1001] = { 0, };		// 각 노드의 진입 간선 수를 저장한 변수

std::vector<int> sortedNodes;		// 위상 정렬로 결정된 방문 순서를 저장한 변수

void topology_sort() {
	for (int count = 1; count <= n; count++) {
		if (inDegree[count] == 0) {
			q.push(count);
			sortedNodes.push_back(count);
		}
	}

	for (int count = 1; count <= n; count++) {
		if (q.empty()) {
			std::cout << "Cyclic graph\n";
		}

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

		for (auto adj : adjacency[curNode]) {
			if ((--inDegree[adj]) == 0) {
				q.push(adj);
				sortedNodes.push_back(adj);
			}
		}
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> n >> k;

	int firstNode, secondNode;
	for (int count = 0; count < k; count++) {
		std::cin >> firstNode >> secondNode;
		adjacency[firstNode].push_back(secondNode);
		inDegree[secondNode]++;
	}

	topology_sort();

	for (auto nodes : sortedNodes) {
		std::cout << nodes << " ";
	}
	std::cout << "\n";
}