[알고리즘] 위상 정렬(Topology Sort)

위상정렬이란?

순서가 정해져있는 작업을 차례로 수행해야 될 경우, 그 순서를 결정하는 알고리즘 이다.

그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것이다.

 

위상정렬 알고리즘

 - 그래프가 존재

 - 그래프에는 노드가 존재하며 각 노드에는 방문 순서가 존재한다.

 - 하나의 그래프에는 여러개의 위상정렬이 가능하다.

 - 위상정렬 도중 그래프에 남아있는 노드 중 incoming이 0인 정점이 없다면, 위상정렬 알고리즘으로 해결할 수 없는 그래프이므로 알고리즘 실행 종료

 - Queue를 이용한다

 - 알고리즘 실행 순서

    1. incoming이 없는 node부터 시작한다.

    2. outgoing node로 이동

    3. outgoing node에서 incoming 숫자 1감소

    4. 해당 node에서 outgoing node로 이동

    5. 2 ~ 4 반복

    6. outgoing으로 이동한 node의 incoming이 0이 될 경우 Queue에 push

 

위상 정렬 예시

//Graph
[[0, 1], [0, 2], [1, 3], [2, 3]]

//incoming, outgoing 형태 
0 : {
   incoming : 0,
   outgoing : [1, 2]
},
1 : {
   incoming : 1,
   outgoing : [3]
},
2 : {
   incoming : 1,
   outgoing : [3]
},
3 : {
   incoming : 2,
   outgoing : []
}

위와 같은 형태의 그래프가 있을 경우 위상 정렬 시 다음과 같다.

0 -> 1 -> 3

   -> 2 -> 3

0 -> 1 -> 2 -> 3 or 0 -> 2 -> 1 -> 3 2개의 결과 모두 위상 정렬이다.

 

struct Solution;
impl Solution {
    pub fn topology_sort(graph: Vec<Vec<i32>>) -> Vec<i32> {
        let mut answer : Vec<i32> = Vec::new();
        //incoming outgoing 저장할 topology Graph
        //incoming count, outgoing node
        let mut v : Vec<(usize, Vec<usize>)> = vec![(0, vec![]); graph.len()];

        println!("그래프 : {:?}", graph);
        //topology Graph 구성
        for p in graph.iter(){
            v[p[1] as usize].0 += 1;
            v[p[0] as usize].1.push(p[1] as usize);
        }
        println!();
        for i in 0..v.len(){
            println!("노드 {} {:?}", i, v[i]);
        }
        println!();

        let mut entry_point: Vec<usize> = Vec::new();
        for (node, i) in (0..).zip(v.iter()) {
            if i.0 == 0 {
                entry_point.push(node);
            }
        }

        //entry_point의 node부터 실행
        while let Some(p) = entry_point.pop(){
            println!("{:?}", p);
            //방문한 노드 push
            answer.push(p as i32);
            for i in v[p].1.clone(){
                //incoming count 감소
                v[i].0 -= 1;
                //incoming node이면 push
                if v[i].0 == 0 {
                    entry_point.push(i as usize);
                }
            }
        }
        println!();
        answer
    }
}

 

CPP코드

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

using namespace std;

template<class T>
class TopologySort{
private:
	queue<T> entry_point;
public:
	TopologySort() {};
	~TopologySort() {
    	while(!entry_point.empty()){
           entry_point.pop();
        }
    };

	vector<T> run(vector<vector<T>> graph) {
		vector<T> answer;
		vector<T> incoming(graph.size());
		vector<vector<T>> outgoing(graph.size());

		for (int i = 0; i < graph.size(); i++) {
			incoming[graph[i][1]]++;
			outgoing[graph[i][0]].push_back(graph[i][1]);
		}
		
		for (int i = 0; i < graph.size(); i++) {
			if (incoming[i] == 0) {
				entry_point.push(i);
			}
		}

		while (!entry_point.empty()) {
			T node = entry_point.front();
			entry_point.pop();
			answer.push_back(node);
			for (int i = 0; i < outgoing[node].size(); i++) {
				incoming[outgoing[node][i]]--;
				if (incoming[outgoing[node][i]] == 0) {
					entry_point.push(outgoing[node][i]);
				}
			}
		}

		return answer;
	}
};