위상정렬 - Githubissues

위상정렬 ( 그래프 정렬 )

위상정렬이 가능하려면 DAG 그래프 여야함!
Directed Acyclic Graph의 약자로 방향성이 있고, 사이클이 없는 그래프
위상 정렬이 필요한 경우는 그래프에서 반드시 자신보다 선행되어야 할 일을 다 끝내야만 작업에 들어갈수 있는 조건이 주어질 때
- 진입차수가 0이라는 것은 자신보다 선행되어야 할 노드 일이 다끝나서 이제 진행해도 된다는 뜻!
예) 대학교 수업 듣는 순서, 스타 건물 짓는 순서

위상정렬 구현 시나리오

1) 인접 리스트 형식의 그래프 생성 한 뒤, 각 노드별로 진입차수를 기록 2) indegree ( 진입차수 ) 0인 노드들을 탐색 후 ==> 큐 삽입 3) 입접리스트 이용하여 이동하면서 방문한 노드는 진입 차수 -1 변경 4) 큐를 이용하여 연결된 노드들을 방문하는데 방문할때마다 degree를 하나씩 낮춰주며 degree 가 0이 되는 노드들을 큐에 넣고 계속하여 탐색

예 ) 가수 출연 순서

1 4 3
6 2 5 4
2 3 == > 6 2 1 5 4 3 또는 1 6 2 5 4 3

참고 링크 : https://m.blog.naver.com/PostView.nhn?blogId=kks227&logNo=220800013823&proxyReferer=https%3A%2F%2Fwww.google.com%2F

사이클 확인

N개의 노드를 한번씩 돌기도 전에 큐가 비어 버린다면 위상 정렬 불가능!!!!!!!
사이클이 생겼다면 싸이클에 속하는 정점들 중엔 indegree가 0인 정점 한개도 없음 즉 N개의 노드들을 한번씩 다 도는지 확인 하던지 indegree 의 값이 전부 0인지 확인 하는 방법


        for(int i=1; i<= N; i++) // inddegree 0 인 노드 큐에 삽입
        {
            if(degree[i] == 0) que.add(i); 
        }
        solve();
        if(!flag) // 사이클 발생 안한 경우 
        {
            for(int i=0; i< temp.size(); i++)
            {
                System.out.println(temp.get(i));
            }
        }

    }
    public static void solve()
    {
        for(int i=0; i< N; i++)
        {
            if(que.isEmpty()) // N 번 돌지 못하고 끝이 나는 것은 사이클 발생 
            {
                System.out.println(0);
                flag = true;
                return;
            }

            int n = que.poll();

            temp.add(n);

            for(int next : adj.get(n))
            {
                degree[next]--;         //연결된 노드 indegree --
                if(degree[next] == 0) // indegree 0 인 노드는 큐에 삽입 
                {
                    que.add(next);
                }
            }
        }
    }

백준 2252 줄세우기 , 1766 문제집 , 2623 음악프로그램, 1516 게임 개발, 1005 acm craft , 9470 strahler 순서

WonYong-Jang / algorithm

위상정렬 #22

위상정렬 ( 그래프 정렬 )

위상정렬 구현 시나리오

사이클 확인

위상정렬 응용 문제

문제 : 색칠 공부