알고리즘19 :: Graph(bfs)
그래프는 정점과 간선으로 이루어진다.
경로는 간선으로 이루어져있으며 이동할수있다.
최단경로가 경로중 가장 짧은것을 의미
가중치가 제일 작은것이 최단경로다
사이클은 시작점 = 도착점
방향이 있으면 역으로 갈수없다.
방향이없으면 간선은 방향이없다. 양방향이다.
방향없는그래프는 저장할수없어서 가는방향, 오는방향을 저장한다.
루프는 돌아오는것
가중치는 간선에 값이있는것이다.
가중치가없으면 1이다.
차수는 연결되어있는 간선의수
방향그래프는 인디그리, 아웃디그리를 나눠서 계산한다.
*그래프 저장방법?
정점과 간선을 저장한다.
정점은 개수를 저장하면된다.
간선은 어떤간선이 있는지 다 저장해야한다.
어떤 정점 x와 연결된간선을 효율적으로 찾기위해서 저장한다.
*인접행렬
1이면 간선이 있고 0은 간선이 없음
방향이없으면 가는방향 오는방향 저장해야 한다.
만약 가중치가있으면 간선이있으면 가중치 없으면 0
*인접리스트
동적인배열이 필요하다.
구현시는 벡터 를 쓴다.
가중치가있으면 가중치도 같이 넣어준다.
방향이없으면 두개 넣어준다.
*공간복잡도
V제곱 인접행렬
간선의개수 인접리스트
인접행렬은 정점1->정점2 O(1) 걸린다.
정점 사이 간선찾기는쉽다. 정점2->정점1 O(1)이걸린다
인접리스트는 "정점" 에있는 간선을 다봐야한다
이때는 "정점"의 차수만큼 걸린다.
인접 리스트는 1만에 찾기어렵다 모든정점을 다찾아야함.
경로는 간선으로 이루어져있으며 이동할수있다.
최단경로가 경로중 가장 짧은것을 의미
가중치가 제일 작은것이 최단경로다
사이클은 시작점 = 도착점
방향이 있으면 역으로 갈수없다.
방향이없으면 간선은 방향이없다. 양방향이다.
방향없는그래프는 저장할수없어서 가는방향, 오는방향을 저장한다.
루프는 돌아오는것
가중치는 간선에 값이있는것이다.
가중치가없으면 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])
'알고리즘' 카테고리의 다른 글
알고리즘22 :: 플러드 필&BOJ_2677_단지번호붙이기 (0) | 2019.02.28 |
---|---|
알고리즘20 :: Graph Search (0) | 2019.02.27 |
알고리즘17 :: BOJ_3053_택시기하학 (0) | 2019.02.26 |
알고리즘16 :: BOJ_13241_최소공배수 (0) | 2019.02.25 |
알고리즘15 :: BOJ_1107_리모컨 (0) | 2019.02.25 |
댓글
이 글 공유하기
다른 글
-
알고리즘22 :: 플러드 필&BOJ_2677_단지번호붙이기
알고리즘22 :: 플러드 필&BOJ_2677_단지번호붙이기
2019.02.28 -
알고리즘20 :: Graph Search
알고리즘20 :: Graph Search
2019.02.27 -
알고리즘17 :: BOJ_3053_택시기하학
알고리즘17 :: BOJ_3053_택시기하학
2019.02.26 -
알고리즘16 :: BOJ_13241_최소공배수
알고리즘16 :: BOJ_13241_최소공배수
2019.02.25