그래프

그래프 구현방법

1. 인접 행렬

- 인접 노드 탐색 시간 복잡도 : O(N) ->  한 행을 다 검색해야 한다

- 에지 탐색 시간 복잡도 : O(1)

2. 연결리스트

- 인접 노드 탐색 시간 복잡도 : O(degree(node)) 

- 에지 탐색 시간복잡도 : O(degree(node))

 

위상정렬의 두가지 방법

1. indegree가 0인 애들을 찾는다. 그리고 outdegree 에지를 제거한 후 이 작업을 반복하면서 연결리스트 뒤에 추가한다.

2. DFS를 이용해 leaf child에 도달했을 때, leaf child를 제거하고 연결리스트 앞에 추가한다..