위상정렬 (Topological Sort)
DAG (Directed Acyclic Graph)
순환(사이클)을 가지지 않는 방향그래프
위상정렬
- DAG에서 방향성을 거스르지 않고 정점들을 나열하는 것
- 각 정점을 우선순위에 따라 배치한 것
- 결과는 유일하지 않다.
- 노드 방문 후 나가는 간선을 지움 (outdegree를 0으로 만듦)
- indegree가 0인 노드부터 다시 반복
indegree가 0인 노드가 여러 개라면 어느 것에서 시작해도 무방하므로 결과가 유일하지 않을 수 있다.
int V; //정점
int E; //간선
boolean[] visited = new boolean[V];
ArrayList<Integer>[] adjList = new ArrayList[V];
int[] indegree = new int[V];
ArrayList<Integer> ordered;
for(int i=1; i<=V; i++) {
adjList[start].add(end);
indegree[end]++;
}
- indegree가 0인 노드부터 시작
- 방문하지 않은 경우 dfs를 수행하면 마지막 노드까지 연결하는 경우가 ordered에 역순으로 저장되게 됨
- ordered를 반대로 정렬하면 startNode부터 마지막 노드까지의 경로가 나옴
- 결과가 1개 나옴
static ArrayList<Integer> topologicalSort() {
ordered.clear();
Arrays.fill(visited, false);
ArrayList<> startNode;
for(int i=1; i<=V; i++) {
if(indegree[i] == 0) {
startNode.add(i);
}
}
for(int i:startNode) {
if(!visited[i]) {
dfs(i);
}
}
Collections.reverse(ordered);
return ordered;
}
DFS를 빠져나오면 가장 마지막 노드에서 끝나게 됨
static void dfs(int u) {
visited[u] = true;
for(int v: adj[u]) {
if(!visited[v]) {
dfs(v);
}
}
ordered.add(u);
}
BFS
DFS로 구현하면 V가 25000 초과 시 스택오버플로우가 발생할 것임.
BFS로 구현해보자!
static void topology_bfs() {
Queue<Integer> q = new ArrayList<Integer)();
for(int i=1; i<=V; i++) {
if(indegree[i] == 0) {
q.offer(i);
}
}
while(!q.empty()) {
int u = q.poll();
ordered.add(u);
visited[u] = true;
for(int v: adjList[u]) {
if(!visited[v]) {
indegree[v]--;
if(indegree[v] == 0) {
q.offer(u);
}
}
}
}
}
Author And Source
이 문제에 관하여(위상정렬 (Topological Sort)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@petitebobo/위상정렬-Topological-Sort저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)