알고리즘19 :: Graph(bfs)

그래프는 정점과 간선으로 이루어진다.
경로는 간선으로 이루어져있으며 이동할수있다.
최단경로가 경로중 가장 짧은것을 의미
가중치가 제일 작은것이 최단경로다
사이클은 시작점 = 도착점

방향이 있으면 역으로 갈수없다.
방향이없으면 간선은 방향이없다. 양방향이다.
방향없는그래프는 저장할수없어서 가는방향, 오는방향을 저장한다.

루프는 돌아오는것
가중치는 간선에 값이있는것이다.
가중치가없으면 1이다.
차수는 연결되어있는 간선의수

방향그래프는 인디그리, 아웃디그리를 나눠서 계산한다.

*그래프 저장방법?
정점과 간선을 저장한다.
정점은 개수를 저장하면된다.
간선은 어떤간선이 있는지 다 저장해야한다.
어떤 정점 x와 연결된간선을 효율적으로 찾기위해서 저장한다.

*인접행렬
1이면 간선이 있고 0은 간선이 없음
방향이없으면 가는방향 오는방향 저장해야 한다.
만약 가중치가있으면 간선이있으면 가중치 없으면 0

*인접리스트
동적인배열이 필요하다. 
구현시는 벡터 를 쓴다. 
가중치가있으면 가중치도 같이 넣어준다.
방향이없으면 두개 넣어준다.

*공간복잡도
V제곱 인접행렬
간선의개수 인접리스트

인접행렬은 정점1->정점2  O(1) 걸린다.
정점 사이 간선찾기는쉽다. 정점2->정점1 O(1)이걸린다
인접리스트는 "정점" 에있는 간선을 다봐야한다
이때는 "정점"의 차수만큼 걸린다.
인접 리스트는 1만에 찾기어렵다 모든정점을 다찾아야함.

인접행렬은 공간이 너무 필요하다. => O(V^2)
인접리스트는 간선을 저장한다. => O(E)간선이 작은것이 많아서 인접리스트를 쓰는게 좋다.
정점의 개수(E) << 간선의개수(V)^2

인접리스트는 있는간선만 저장한다.
인접리스트가가 인접행렬보다 빠르다.

완전그래프 그래프 모든 정점사이 간선 존재.
완그는 인접행렬좋다.
E<<V^2

* 간선리스트
인접리스트는 vector나 arrayList자료구조 써야댐
그게 아니면 LinkedList를  직접 구현해야한다. 
간접리스트를 쓰면 인접리스트와 비슷한 효과를 낼 수 있다. 
간접리스트는 정점과 다른 정점간의 간선으로 연결된 각각의 정점을 리스트에 저장한다.A[0] = 1 2, A[1]= 1 5 저장을 하면 정점에 개수에 따라 cnt 라는 배열을 생성하여 저장한다. A[0] = 1 2, A[1] = 1 5 이러면 i가 1인 값은 2개가 된다. cnt[1] = 2 이런식으로 표로 만들고 누적해준다. 0 2 3 1 3 2 1 이러면0 2 5 6 9 11 12 이렇게 된다. => 인접리스트, 인접행렬 은 임의의 한정점에서 시작하는 모든 간선을 찾기 위해서 이다. 2에서 시작하는 간선은 2번째 index부터 5번째 index 전까지 (A[2] ~ A[5])