hyeoneee's blog

어떤 일을 하는 순서를 찾는 알고리즘이다.

DAG 란

1. 노드간의 순서가 있을때 

2. 사이클이 없을때 -> 사이클 판단 가능

3. 시간복잡도 O(V+ E)

dfs , bfs 모두 가능하다. bfs로 구현해보도록 하겠다.

DAG는 노드간의 순서가 있기 때문에

진입차수가 0인것을 queue에 넣어서 BFS를 진행해 보도록 하겠다.

Dfs

	for( n of All){
		if(!visited[n]) dfs(n);
	}
	
	dfs(int now){
		visited[now] = true;
		for(next : adj){
			if(!visited[next]) dfs(next);
		}
		stack.push(now);	//dfs 나오는 순서대로 stack에 쌓아준다. 
	}

Bfs

  static int bfs() { //위상정렬 DAG
        Queue<Integer> q = new ArrayDeque<>();
        int cnt = 0; 
       		
         for(int i = 1 ;i <= indegree.size()-1 ; i ++){
			if(indegree[i]==0){ // 인디그리가 없으면 큐에 넣어준다.
				q.add(i);
           }
	}

        while (!q.isEmpty()) {
            int now = q.poll();
            cnt++;
            for (Node next : adj[now]) {
                indegree[next.n]--; //next에 방문했으니 진입차수 줄여주기
                // next에 오기까지 위한 최대 dist 구해주기 그래야 다음을 갈 수 있음
                dist[next.n] = Math.max(dist[next.n], dist[now] + next.cost);
                if (indegree[next.n] == 0) {
                    q.add(next.n);
                }
            }
        }
        
        return cnt != N // cnt가 N이 아니면 사이클이 있음
    }

응용

1. 순서 찾기

2. 사이클 찾기

3. 문제 조건에 따라 순서 부여해 풀기

4. 위상정렬 + 동적 계획법

5. 사이클 없애가는 문제