자료구조 Graph

== Graph 기본 개념 정리 ==

- Direct Graph

  - vertax 와 edge 가 있으면 Graph 라고 한다

  - 방향성이 있으니 Direct Graph

- Undirect Graph

  - 방향성이 없다.

- Weighted Graph

  - edge에 cost가 있을 때

- Vertex List   vertaxList = ['0', '1', '2', '3', '4', '5']   - Edge List   edgeList = [(0,1), (1,0), (1,2), (1,3), (2,1),                   (3,1), (3,4), (4,3), (4,5), (5,4)]   - Undirect graph 이니 양쪽 방향 다 있지. - Adjacency List   adjacencyList = [[1], [0,2,3], [1], [1,4], [3,5], ]   - 장점 : 공간복잡도가 낮다. O(#edge)              BFS나 DFS에서 활용

- Adjacency Matrix

  - edge가 있으면 1 없으면 0

  - 장점 : edge가 있는지 없는지 1번의 검색으로 알 수 있다. 

  - 단점 : 공간복잡도가 높다.  O(n^2)