유향 그래프의 위상 정렬 또는 위상 순서는 정점 u에서 정점 v까지의 모든 유향 모서리 UV에 대해 u가 순서에서 v 앞에 오도록 정점의 선형 순서입니다. 이것은 유향 그래프에서만 의미가 있습니다.
토폴로지 정렬이 의미가 있는 곳이 많이 있습니다. 예를 들어 레시피를 따르고 있다고 가정해 보겠습니다. 여기에는 다음 단계로 이동하기 위해 반드시 거쳐야 하는 몇 가지 단계가 있습니다. 그러나 이들 중 일부는 병렬로 수행될 수 있습니다. 비슷한 방식으로 대학에서 과정을 선택할 때 추가 과정의 전제 조건이 될 수 있는 고급 과정에 대한 몇 가지 전제 조건이 있습니다. 예를 들어 -
예시
/** * CS101 CS102 * / \ / * CS204 CS340 * \ /| \ * CS380 | CS410 * \ | / * CS540 */
위의 그래프에서 한 레벨의 코스를 수강하려면 먼저 상위 레벨에서 연결된 모든 코스를 수강해야 합니다. 다음은 위 그래프에 대해 가능한 토폴로지 정렬입니다.
CS101 -> CS204 -> CS102 -> CS340 -> CS410 -> CS380 -> CS540 CS102 -> CS101 -> CS340 -> CS204 -> CS410 -> CS380 -> CS540
이것을 자바스크립트로 구현해보자. 그래프를 재귀적으로 표시하고 탐색하는 데 도움이 되도록 토폴로지 정렬 및 topologicalSortHelper의 2가지 함수를 작성합니다.
예시
topologicalSortHelper(node, explored, s) {
explored.add(node);
// Marks this node as visited and goes on to the nodes
// that are dependent on this node, the edge is node ----> n
this.edges[node].forEach(n => {
if (!explored.has(n)) {
this.topologicalSortHelper(n, explored, s);
}
});
// All dependencies are resolved for this node, we can now add
// This to the stack.
s.push(node);
}
topologicalSort() {
// Create a Stack to keep track of all elements in sorted order
let s = new Stack(this.nodes.length);
let explored = new Set();
// For every unvisited node in our graph, call the helper.
this.nodes.forEach(node => {
if (!explored.has(node)) {
this.topologicalSortHelper(node, explored, s);
}
});
while (!s.isEmpty()) {
console.log(s.pop());
}
} 다음을 사용하여 테스트할 수 있습니다.
예시
let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");
g.addNode("E");
g.addNode("F");
g.addNode("G");
g.addDirectedEdge("A", "C");
g.addDirectedEdge("A", "B");
g.addDirectedEdge("A", "D");
g.addDirectedEdge("C", "D");
g.addDirectedEdge("D", "E");
g.addDirectedEdge("E", "F");
g.addDirectedEdge("B", "G");
g.topologicalSort(); 우리가 만든 그래프는 다음과 같습니다 -
예시
/** * A * / | \ * C | B * \ | | * D G * | * E * | * F */
출력
이것은 출력을 줄 것입니다 -
A B G C D E F