2018-01-01

##위상정렬은 DAG(방향있는, 싸이클 없는, 그래프) 에서 방법 2가지

- BFS : indegree 0인 지점부터 방문하면서, 방문할때 indegree 감소하고 0이면 queue 에 넣기.

- DFS : 방문하지 않은 모든 정점 DFS 하면서, DFS 종료시 배열에 저장하고, 나중에 역순으로 출력.

##오일러 서킷/ 오일러 트레일 (서킷은 시작점=끝점, 트레일은 시작점 != 끝점)

- 정점의 차수(degree의 개수가 중요)

- 무향 그래프에서 오일러 서킷 - 모든 정점의 차수가 짝수, 하나의 컴포넌트로 이루어져 있어야함.

                     

   오일러 트레일 - 시작점 ,끝점의 차수가 홀수, 나머지 정점 짝수 하나의 컴포넌트로 이루어져 있어야함.

    

- 유향 그래프에서 오일러 서킷 - 모든 정점의 in-degree 와 out-degree가 같고, 하나의 컴포넌트로 이루어져 있어야함.

   오일러 트레일 - 시작점은 out-degree 가 한개 더 많고, 끝점은 in-degree 가 한개 더 많아야함, 

                         나머지 정점은 in-degree와 out-degree가 같아야하고, 하나의 컴포넌트로 이루어져 있어야함.

- 오일러 서킷/트레일 구하는 방법- DFS를 수행하면서 DFS가 종료될 때, 경로를 추가한다. 

                                              (무향 그래프에서는 순서가 상관없지만, 유향 그래프에서는 역순으로 출력)

##깊이 우선 탐색에서 간선의 분류 방법(참고용 페이지)

무향 그래프 - 교차간선X, 역방향간선=순방향간선

유향 그래프 - 교차간선, 역방향간선, 순방향간선