Topological Sorting(위상정렬) 이란 |
위상정렬은 유향그래프(방향그래프)의 꼭짓점들을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다.
위상정렬을 가장 잘 설명하는 예는 선수과목의 구조를 예로 들 수 있다. 특정 수강과목에 선수과목이 있다면 그 선수과목을 먼저 수강해야 하므로 특정과목을 수강해야 할때 위상정렬을 통해 올바른 수강순서를 찾아 낼 수 있다.
Topological Sorting(위상정렬) 조건 |
- 사이클이 없는 유향 그래프
Topological Sorting(위상정렬) 특징 |
- 모든 정점을 일렬로 나열
- 정점 x에서 정점 y로 가는 간선이 있다면 x는 반드시 y보다 앞에 위치한다.
- 일반적으로 임의의 유향 그래프에 대해 복수의 위상 순서가 존재한다.
Topological Sorting(위상정렬) 에서의 간선의 의미 |
- 순방향 간선 : 순차적으로 찾아가는 간선
- 역방향간선 : 자손에서 선조로 이어지는 간선
Topological Sorting(위상정렬) 알고리즘 |
- 큐를 활용한 위상정렬
- 진입차수가 0인 정점을 큐에 삽입합니다. 위의 그림에서 1
- 큐에서 원소를 꺼내 연결된 모든 간선을 제거합니다.
- 간선 제거 이후에 진입차수가 0이 된 정점을 큐에 삽입합니다. 위의 그림에서 2,3
- 큐가 empty를 만날때 까지 같은 동작을 반복합니다.
- 이 경우 위의 그림에서는 다음과 같이 큐에 들어 갑니다.
- 스택을 활용한 위상정렬
- DFS를 이용하여 1에서 출발을 합니다.
- 가장 마지막 위치까지 방문을 합니다.
- 스택에 해당 번호를 쌓고 바로 위로 빠져 나옵니다.
- 이것을 계속 반복한 후 마지막 에 스택에 쌓인 수를 출력합니다.
- 위의 그림을 처리하는 순서를 나타냅니다.
- 위의 그림을 처리하는 순서를 나타냅니다.
위상정렬에서 사이클이 있는지 판단하기 |
- 큐를 활용한 위상정렬에서 사이클이 있는지 판단하기
- 큐에서 모든 정점을 방문하지 않았는데 큐가 비어 있다면 사이클이 발생하는 것이다.
- 맨 처음 그림을 예를 들어 살펴 보자.
- 스택을 활용한 위상정렬에서 사이클이 있는지 판단하기
- 스택에 데이터가 없는데 방문했던 정점이라면 사이클이 발생하는 것이다.
- 맨 처음 그림을 예를 들어 보자.
문제풀이 |
백준 2252번 줄세우기
- 큐를 이용해 문제풀이
-
더보기더보기더보기
#include <bits/stdc++.h> using namespace std; #define MAXN 32000 vector <int> vt[MAXN+1]; queue <int> q; int n,m; int inDegree[MAXN+1]; int main() { cin >> n >> m; for(int i=0;i<m;i++) { int x,y; cin >> x >> y; vt[x].push_back(y); inDegree[y]++; } for(int i=1;i<=n;i++) { if(inDegree[i]==0) q.push(i); } vector <int> res; while(!q.empty()) { int x = q.front(); res.push_back(x); q.pop(); for(auto i:vt[x]){ ///x에 연결된 경로이 진입차수를 하나씩 제거 한다. if(--inDegree[i]==0) q.push(i); } } for(auto i : res){ cout << i << " "; } return 0; }
-
- 스택을 이용해 문제풀이
-
더보기더보기더보기
#include <bits/stdc++.h> using namespace std; #define MAXN 32000 vector <int> vt[MAXN+1]; stack <int> st; int n,m,visit[MAXN+1]; void dfs(int v) { if(visit[v]) return; visit[v] = 1; for(int i=0;i<vt[v].size();i++) { dfs(vt[v][i]); } st.push(v); } int main() { int i; cin >> n >> m; for(i=0;i<m;i++) { int x,y; cin >> x >> y; vt[x].push_back(y); } for(i=1;i<=n;i++) { if(!visit[i]) dfs(i); } while(!st.empty()) { cout << st.top() << ' '; st.pop(); } return 0; }
-
사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 통신판매신고번호 : 호 | 사이버몰의 이용약관 바로가기
'강의자료 > 알고리즘' 카테고리의 다른 글
SCC(Strongly Connected Components)-코세라주 알고리즘 (8) | 2022.03.23 |
---|---|
최소 공통조상 LCA(Lowest Common Ancestor) 알고리즘 (12) | 2022.02.08 |
[자료구조]트라이(TRIE) (11) | 2022.01.07 |
[자료구조] 비트마스크(bitmask)_II (12) | 2021.12.22 |
[자료구조] 비트마스크(bitmask)_I (10) | 2021.12.14 |