순환없는방향성그래프(DAG) 에서 사용할 수 있는 위상정렬(Topological Sort) [순서적공정모델링]

Acyclic(에싸이클릭) = 비순환

즉 강한결합요소가 없는 그래프이다

(강한결합요소 = 순환)

왼쪽 그림 순환, 오른쪽 그림 비순환

[공정모델링]

오른쪽 그림에서 A 가 완료 되어야 E,D,C,B 를 할 수 있고

B 와 D 가 완료 되어야 C 를 할 수 있다

F는 D 가 완료 되어야 할 수 있다

왼쪽 그래프는 공정모델링이 안된다 순환됨으로 개념적으로 끝나는 부분이 없다

선행작업 : 먼저 이루어져야 하는 작업

왼쪽 처럼 표를 만들고 나면 오른쪽 처럼 그래프로 만들 수 있다

D,G,L 작업이 끝나야만 모든 작업이 끝날 수 있다

시작은 A 하나

(D,E,F,G) 등이 동시에 공정이 진행 될수 있는 부분

(H,I,J)

위와 같은 그래프를 AOV Network 이라 한다

---

위상정렬 : 동시에 하지 않고 혼자서 어떤 순서로 공정을 거처야 하는가? 를 결정하는 것

비선형 모양을 순서대로 나열 하는 것

ex)G는 마지막이니 제일 나중에 해도 된다

indegree : 공정의 시작( 내차수 )

outdegree : 공정의 끝나는 지점들 ( 외차수 )

[위상정렬]

하는 법은 A 를 접근한 후 B 의 내차수는 1 이니 A->B 로 연결되는 간선을 없애고 B 의 내차수 는 들어오는 선이 1 이니 이것을 0 으로 만들어서

B 는 이제 위의 공정에서 시작점이 된다 (반복)

C 를 지울때 C 와 연결된 간선을 모두 지운다

그러면 D,E,F,G 들은 내차수가 0 이 됨으로 D,E,F,G 를 큐에 넣는다

D 를 큐에서 빼내고 D를 방문한 다음에 D 를 지우고

E를 큐에서 빼고 방문한다음 E 와 인접한 K 와의 간선을 지운다 하지만 K 의 내차수 0 이 아님으로 아직 큐에 넣지 않는다

그다음 F 가 없어지면 연결된 노드들의 차수는 0 이 되고 이 노드들을 큐에 넣고, 위 과정 반복...

[큐에서 나올때 방문한다]

[내차수가 0 이 되면 큐에 넣는다]

[역위상]

외차수가 0 인점을 선택해서 위상의 반대로 실행해준다

위상정렬을 위해 큐나, 스택을 사용하면 된다

[큐에서 나올때 방문한다]

[외차수가 0 이 되면 큐에 넣는다]