위상 정렬(Topological Sorting)

위상 정렬(Topological Sorting)

☀️ 위상 정렬이란?

순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다.

큐, 스택 자료구조를 이용하여 구현이 가능하다.

☀️ 위상 정렬의 처리 방식

☀️ 구현 방법

1️⃣ 그래프의 구성

class Graph { class Node { int data; LinkedList adjacentNodes; int indegree; Node(int data) { this.data = data; adjacentNodes = new LinkedList(); this.indegree = 0; } } Node[] nodes; Graph(int size) { nodes = new Node[size]; for (int i = 0; i < size; i++) nodes[i] = new Node(i); } }

ㆍ 그래프가 가지고 있는 노드의 정보를 클래스로써 정의하였다.

ㆍ 각각의 노드는 데이터(data), 인접한 노드들(adjacentNodes), 진입 차수(indegree)를 가지고 있다.

2️⃣ 엣지를 구성해주는 메서드

void addEdge(int index01, int index02) { if (!nodes[index01].adjacentNodes.contains(nodes[index02])) nodes[index01].adjacentNodes.add(nodes[index02]); nodes[index02].indegree++; }

ㆍ index01, index02의 관계를 가지는 두 노드를 매개변수로 입력받는다.

ㆍ index01 노드의 adjacentNodes에 index02 노드를 추가해준다.

ㆍ 추가로 index02 노드의 진입 차수를 1만큼 증가시킨다.

3️⃣ 큐 자료구조를 이용한 위상 정렬 알고리즘

void topologicalSort() { Queue queue = new LinkedList(); for (int i = 0; i < nodes.length; i++) if (nodes[i].indegree == 0) queue.add(nodes[i]); while (!queue.isEmpty()) { Node returnNode = queue.poll(); System.out.print(returnNode.data + " "); for (Node node : returnNode.adjacentNodes) { node.indegree--; if (node.indegree == 0) queue.add(node); } } }

ㆍ 우선, 큐 자료구조에 진입 차수가 0인 노드들을 삽입한다.

ㆍ 큐에서 노드를 꺼낸 후 해당 노드의 데이터를 출력한다.

ㆍ 큐에서 꺼낸 노드의 인접한 노드들의 진입 차수를 1만큼 감소시킨다.

ㆍ 진입 차수가 0인 인접한 노드들을 큐에 삽입한다.

ㆍ 위 과정을 큐에 데이터가 없을 때까지 반복한다.

from http://qlsdud0604.tistory.com/27 by ccl(A) rewrite - 2021-09-25 18:26:25