위상정렬 (Topological Sort)

DAG (Directed Acyclic Graph)

순환(사이클)을 가지지 않는 방향그래프

위상정렬

• DAG에서 방향성을 거스르지 않고 정점들을 나열하는 것
• 각 정점을 우선순위에 따라 배치한 것
• 결과는 유일하지 않다.

1. 노드 방문 후 나가는 간선을 지움 (outdegree를 0으로 만듦)
2. 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]++;
}

1. indegree가 0인 노드부터 시작
2. 방문하지 않은 경우 dfs를 수행하면 마지막 노드까지 연결하는 경우가 ordered에 역순으로 저장되게 됨
3. ordered를 반대로 정렬하면 startNode부터 마지막 노드까지의 경로가 나옴
4. 결과가 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);
                }
            }
        }
    }
}