[알고리즘] Topology Sort

치치·2025년 1월 24일

알고리즘

알고리즘C++

목록 보기

17/24

위상 정렬

순서가 정해져있는 작업을 순서대로 수행해야 할 때, 그 순서를 결정해주는 알고리즘이다
각 정점들의 간선의 방향에 따라 선행 순서를 지키면서 모든 정점을 차례로 진행한다
-> 어떤 작업을 수행하려면 다른 작업이 먼저 끝나야한다는 의미

쉽게 말하자면, 간선의 방향 순서를 지키면서 순서대로 정렬하는 알고리즘이다
예를 들어, 대학교 과제 발표 순서를 보자
-> 선행 순서는 자료조사 -> PPT 제작 -> 발표 순서이다
-> 자료조사를 수행하지 않으면 PPT 제작을 할 수 없다
-> 마찬가지로, PPT 제작을 하지 않으면 발표를 할 수 없다

발표를 하기 위해서 앞에 수행해야하는 작업 순서를 구해주는 것이 바로 위상 정렬이다!

위상 정렬 구현에 앞서,,,

비순환 단방향 그래프

위상정렬은 방향 그래프에서 사용된다
사이클이 발생하는 경우 사용할 수 없다
-> 사이클이란?
각 정점끼리 방향이 이어져서 순환되는 모양

위상정렬에서는 사이클이 존재하지 않는 방향그래프에서 사용된다

비순환 단방향 그래프 (DAG) - Directed Acyclic Graph

진입차수

진입차수란?

정점에 들어오는 간선의 개수이다
-> 사진 속 그래프에서 간선의 방향을 잘 보면 알 수 있다
A에 들어오는 간선은 2개 -> 진입차수 2
B에 들어오는 간선은 0개 -> 진입차수 0
C에 들어오는 간선은 1개 -> 진입차수 1
D에 들어오는 간선은 2개 -> 진입차수 2

** (위의 그래프는 진입차수의 예를 들기 위한 그림일 뿐, 사이클과는 관련이 없다)

이제 위상정렬에 필요한 개념을 다 알았으니 위상정렬을 구현해볼 수 있다

위의 내용을 바탕으로 위상정렬은 진입차수가 0인 정점을 출력하고, 이 정점과 연결된 간선들을 제거하면서 정렬을 반복하는 알고리즘인 것이다

위상정렬 첫 구현 (틀린 답안)

처음 구현했을때 결과값이 다르게 나와서 문제점을 찾아보았다

제대로 된 결과값은 1 2 5 3 4 6 7 이지만 나는 4와 6이 반대로 나왔다

출력이 잘못 나온 이유 중 큰 문제는 아마 문제점2였던 거 같다

문제점 1: 아래의 코드에서 진입차수가 0이면 큐에 삽입해야 하는데 나는 진입차수가 0이 아닌 것들은 큐에 넣었다 (완전 잘못된 거 같은데)
문제점 2: 큐에 넣은 뒤 진입차수를 0으로 만들었다
-> 이럴 경우 진입차수가 2였던 정점6의 진입차수가 0이 되어버림 (순서가 이상해진다)
문제점 3: 맨 처음 시작에서 진입차수가 0인 정점을 넣어야하는 데, 나는 진입차수 배열의 [0]가 0일 경우 큐에 정점값을 넣어주었다
-> 어차피 진입차수가 0인게 정점1뿐이라 현재는 상관없지만, 만약 진입차수가 0인 정점이 여러개일 경우 다 판단해서 큐에 다 삽입해야한다

위상정렬 전체코드 (정답 답안)

진입차수가 0인 정점을 Queue에 삽입한다
Queue에서 원소를 꺼내 연결된 모든 간선을 제거한다
간선 제거 이후에 진입 차수가 0이 된 정점을 Queue에 삽입한다
Queue가 빌 때까지 2번 ~ 3번을 반복한다

진입차수를 담아줄 배열
-> 정점의 수와 동일한 인덱스에 담아 주기 위해서 0번째는 사용하지 않는다

정점을 담을 큐 자료구조
-> Queue는 선입선출 구조
그래프를 저장할 벡터 배열
(자료구조때 배운 그래프가 잘 기억이 나지 않아서 다시 복습해야할듯..)
-> 아래의 그림은 깊이우선탐색< 포스트에 기록되어있음
https://velog.io/@yangju058/알고리즘-깊이-우선-탐색-DFS

`void Sort()`

첫 시작은 진입차수가 0인 정점들을 탐색하여 큐에 모두 삽입한다
큐가 비지 않았을때, 임시변수 x에 큐에 가장 앞의 값을 넣어 두고 출력한다
큐에서 해당 정점의 값을 뺀 뒤 해당 정점과 연결된 정점들을 탐색한다
-> 연결된 정점의 간선을 제거한다 -1
-> 간선 제거한 뒤 그 정점의 진입차수가 0이 된다면 큐에 삽입하고 그렇지 않다면 건너뛰기

#include <iostream>
#include <queue>
#include <vector>
#define SIZE 8
using namespace std;

class Graph
{
private:
	int degree[SIZE]; // 진입차수 배열
	queue <int> queue; // 인접 리스트
	vector <int> graph[SIZE]; // 그래프 저장  

public:
	Graph()
	{
		for (int i = 0; i < SIZE; i++)
		{
			degree[i] = NULL;
		}
	}

	// 방향 그래프 (간선을 연결하고 진입을 당하는 노드(edge)의 진입차수 배열에 ++)
	void Insert(int vertex, int edge)
	{
		graph[vertex].push_back(edge);
		degree[edge]++;
	}

	void Sort()
	{
		for (int i = 1; i < SIZE; i++)
		{
			if (degree[i] == 0)
			{
				queue.push(i);
			}
		}

		while (!queue.empty())
		{
			int x = queue.front();

			queue.pop();

			cout << x << " ";

			for (int i = 0; i < graph[x].size(); i++)
			{
				int start = graph[x][i];

				// 간선을 먼저 제거한 뒤
				degree[start]--;

				// 큐에 넣어줘야 함
				if (degree[start] == 0)
				{
					queue.push(start);
				}
			}
		}
	}
};

int main()
{
#pragma region 위상 정렬
	
	Graph graph;

	graph.Insert(1, 2);
	graph.Insert(1, 5);

	graph.Insert(2, 3);
	graph.Insert(3, 4);

	graph.Insert(4, 6);

	graph.Insert(5, 6);
	graph.Insert(6, 7);

	graph.Sort();

#pragma endregion
	return 0;
}

출력값:

위상정렬 그림으로 자세히

진입차수가 0인 정점은 1밖에 없기 때문에 1을 큐에 삽입한다.
임시 변수 x에 값을 저장해두고 큐에서 해당 정점을 제거한다.
x값을 출력하고 해당 정점과 연결된 간선을 제거한다.
-> 이제 정점 2와 5의 진입차수가 0이 되었다
진입차수가 0이 된 2와 5를 큐에 삽입했다.
동일하게 큐의 맨 앞의 값을 x에 넣고 큐에서 제거한다.
x값을 출력하고, 2와 연결된 정점들의 간선을 제거한다.
-> 여기서 연결된 정점은 3이고 간선을 제거하여 진입차수가 0이 된다.
진입차수가 0이 된 3을 큐에 삽입한다.
가장 앞의 값인 5를 임시변수 x에 넣어두고 큐에서 제거한다.
x를 출력하고, 5와 연결된 정점의 간선을 제거한다.
-> 여기서 정점5와 연결된 정점은 6이다. 6의 간선을 제거하였지만, 6의 진입차수가 아직 0이 아니기 때문에 큐에 넣지 않고 다음 정점을 탐색한다.
큐의 가장 앞의 값인 3을 변수 x에 넣어둔 뒤, 다시 큐에서 제거한다.
x의 값을 출력하고, 정점3과 연결된 간선을 제거한다.
-> 여기서 정점3과 연결된 정점은 4이다. 4의 진입차수가 0이 된다.
진입차수가 0인 4가 큐에 삽입되었다.
가장 앞의 값인 4를 x에 넣고, 큐에서 제거한다.
x의 값을 출력한 뒤, 정점4와 연결된 간선을 제거한다.
-> 정점4와 연결된 정점은 6이다. 6의 진입차수도 이제 0이 되었기 때문에 큐에 삽입한다.
큐의 가장 앞의 값인 6도 앞에 과정과 마찬가지로 x에 담아주고 큐에서 빼고 값을 출력한다.

7. 마지막 정점7도 똑같은 방식이다.
다음 7과 연결된 정점을 탐색 해야하지만,
7과 연결된 정점이 없어서 반복문을 진행할 수 없다
-> graph[x].size(); == 0 이다
반복문을 종료하고, 큐가 모두 비었기 때문에 while문의 조건도 만족하지 않아서 종료한다.

위상정렬 시간복잡도

O(V + E)
V : 정점의 수
E : 간선의 수

1. 각 정점의 진입차수를 계산 (간선을 한번씩 확인)
2. 시작 시 진입 차수가 0인 정점을 큐에 삽입 (정점만큼 다 확인)

전체 그림

위상정렬 코드 다시보기

다시 코드를 짜보았는데 또,, 실수가 많았다
다시 한번 봐보자

#include <iostream>
#include <queue>
#include <vector>
#define SIZE 7
using namespace std;

// 위상 정렬 (Topology Sort)
// 연결된 간선들을 제거해나가면서 정렬하는 알고리즘
// 방향 그래프에서 사용하여, 진입차수가 0인 노드의 값을 큐에 삽입


class Graph
{
private:
	int degree[SIZE]; // 1. 진입차수 배열

	queue <int> queue; // 2. 큐

	vector <int> graph[SIZE]; // 3. 그래프 - 인접리스트 (연결정보를 담음)


public:
	Graph()
	{
		for (int i = 0; i < SIZE; i++)
		{
			degree[i] = 0;
		}
	}

	// 정점을 간선으로 연결 -> 방향 그래프
	void Insert(int x, int y)
	{
		graph[x].push_back(y);
		degree[y]++;
	}

	void Sort()
	{
		// 진입차수가 0인 노드들의 값 큐에 삽입
		for (int i = 1; i < SIZE; i++)
		{
			if (degree[i] == 0)
			{
				queue.push(i);
			}
		}

		// 큐가 빌때까지 반복
		while (!queue.empty())
		{
			// 큐의 가장 앞의 값 저장
			int x = queue.front();

			cout << x << " ";

			queue.pop();

			for (int i = 0; i < graph[x].size(); i++)
			{
				int next = graph[x][i];
				// 간선 제거 후 큐에 삽입

				degree[next]--;

				if (degree[next] == 0)
				{
					queue.push(graph[x][i]);
				}
			}
		}
	}
};


int main()
{
	Graph graph;

	graph.Insert(1, 4);
	graph.Insert(6, 2);
	
	graph.Insert(4, 3);
	graph.Insert(2, 3);
	graph.Insert(2, 5);

	graph.Insert(5, 4);

	graph.Sort();

	// 결과값 
	// 1 6 2 5 4 3
	// 6 1 2 5 4 3


	return 0;
}

구현 실수

1. 첫시도에 잘못된 부분이 너무 많았다
  -> 큐에 넣는 값부터가 잘못됨. 나는 진입차수가 0인 노드의 값을 넣으려고 했는데, 왜 진입차수의 값을 넣은거지??
  -> 이렇게 되면 처음 진입차수가 0인 노드1과 6의 진입차수 0이 큐에 들어간거임..
1. 방문배열을 사용해서 해당 그래프와 연결된 정점이 방문되지 않았다면 그 정점과 연결된 간선을 제거하려고 했는데, 방문배열이 필요하지 않음
  -> 어차피 방향 그래프이기 때문에 연결된 정점만 확인하면 되더라
1. 두번째 구현
  -> 진입차수를 큐에 넣은 게 아닌, 제대로된 노드값을 넣었다 queue.push(i);
  -> 큐에 삽입할 다음 노드의 값은 next로 해도되고 graph[x][i]로 해도된다 (둘 다 같은 의미)
  여기서 결과값이 1 6 2 5 4 3 이 나오는데, 실제로 큐에 넣는 순서가 1이냐 6이냐에 따라 결과값이 바뀌긴 한다
  -> 하지만 여기서 큐에 넣는 순서가 for int i = 1부터기 때문에, 더 작은 값인 1이 큐에 먼저 삽입된다