위상정렬 알고리즘

내가 이해한 위상정렬을 간단하게 정리해 보겠다.

 

위상정렬은 순환하지 않는  비순환 방향 그래프 에서만 가능하다.

 

 

 

https://ko.wikipedia.org/wiki/%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC

위상정렬 - 위키백과, 우리 모두의 백과사전

 

 

위상정렬의 구현방법은 정말 간단한 순서로 알수있다.

 

1. 자신을 가리키는 간선이  없는 노드 들을  큐에 넣어준다.

2. 큐에 있는 노드를 받아준다.

3. 노드가 가리키는 간선을 지워준다.

 반복

 

 

위상정렬의 경우

순서가 얼마든지 바뀔수있다. 예를들면

 

위의 경우 1,3,2,5,4 일수있지만 

2번 노드의 간선을 지운뒤 5와 4는 얼마든지 바뀔수 있다.

 

 

 

따라서 정답은 13254 와 13245 31245  31254 가 될수있다.

 

 

 

여기서 보이는 특징은

13 은 바뀔수 있지만  {13},{ 2} ,{ 54 }는 서로 바뀌지않는다.

 

만약 위의 예시로  작은순으로 모아야 하는경우

 

13 2 54 가 나온다. 이러한 문제는 

 

백준 : 문제집 1766번  정답비율 48.903% 문제에서 접할수있다. 

 

 

	//노드 간선수
    int a = 0, b = 0;
	cin >> a >> b;
	
    // 노드를 담을 queue
    queue<int> q;
	// v =  자신을 가리키는 간선 수
    vector<int> v(a + 1);
    // va = 배열로 만든 그래프
	vector<vector<int>> va(a + 1);
    
	vector<int>answer;
    
    
	int x = 0, y = 0;
	for (int i = 1; i <= b; i++) {
		cin >> x >> y;
        //그래프 추가
		va[x].push_back(y);
		// 간선 수 추가
        ++v[y];
	}
    
    //가리키는 간선이 없는 노드 큐에 추가
	for (int i = 1; i < v.size(); i++) {
		if (v[i] == 0) {
			q.push(i);
		}

	}
    
    
    // 큐에 노드가 없을때까지 반복
    //만약 큐에 노드가 없지만 모든 노드를 확인하지 않은경우 사이클이 존재함
	while (!q.empty())
	{
    // v_n 노드 번호
		int v_n = q.front();
		q.pop();
        
		cout << v_n<<"\n";
		
        //노드 가 가리키는 노드들
        for (auto i : va[v_n]) {
            //간선수 지워주기
			v[i]--;
            
            //만약 지워준 노드를 가리키는 간선이 더이상 없을경우 queue에 추가
			if (v[i] == 0) {
				q.push(i);
			}
		}
	}

 

 

위상정렬 백준 문제

https://www.acmicpc.net/problem/2252

2252번: 줄 세우기