위상 정렬

방향성 비순환 그래프의 위상 정렬은 정점의 선형 순서입니다. 방향 그래프의 모든 모서리 U-V에 대해 정점 u는 순서에서 정점 v보다 먼저 옵니다.

소스 정점이 대상 정점 다음에 올 것이라는 것을 알고 있으므로 스택을 사용하여 이전 요소를 저장해야 합니다. 모든 노드를 완료한 후 스택에서 간단히 표시할 수 있습니다.

입력 및 출력

입력:0 0 0 0 0 00 0 0 0 0 00 0 0 1 0 00 1 0 0 0 01 1 0 0 0 01 0 1 0 0 0출력:토폴로지 정렬 순서 이후의 노드:5 4 2 3 1 0 
알고리즘
 

 topoSort(u, 방문, 스택) 
 

 입력 - 시작 정점 u, 방문한 노드를 추적하기 위한 배열. 노드를 저장하는 스택입니다. 
 출력 - 스택의 정점을 토폴로지 순서로 정렬합니다.
 
u에 인접한 모든 정점 v에 대해 u를 방문한 것으로 표시하기 시작하고 v가 방문되지 않은 경우 수행한 다음 topoSort(c, 방문, 스택) 완료 u를 stackEnd로 푸시합니다.
 

 topologicalSorting(그래프) 수행 
 

 입력 - 주어진 방향성 비순환 그래프. 
 출력 - 노드의 순서입니다.
 
시작은 처음에 그래프의 모든 노드 v에 대해 모든 노드를 방문되지 않은 것으로 표시하고 v가 방문되지 않은 경우 수행한 다음 topoSort(i, 방문, 스택) 팝을 완료하고 stackEnd의 모든 요소를 ​​인쇄합니다.
 
예시
 
#include#include#define NODE 6 네임스페이스 std;int 그래프 사용[NODE][NODE] ={ {0, 0, 0, 0, 0, 0}, {0, 0, 0 , 0, 0, 0}, {0, 0, 0, 1, 0, 0}, {0, 1, 0, 0, 0, 0}, {1, 1, 0, 0, 0, 0}, {1, 0, 1, 0, 0, 0}}; 무효 topoSort(int u, bool 방문[], 스택&stk) { 방문[u] =true; //노드 v가 방문한 것으로 설정 for(int v =0; v stk; bool vis[노드]; for(int i =0; i 
출력
 
토폴로지 정렬 순서 이후의 노드:5 4 2 3 1 0