Graph란?
-여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조
-즉, 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조이다.
Ex) 두지점간의 최단 경로, 컴퓨터 통신만, sns의 친구관계 등
표현방식
인접리스트
인접리스트는 그래프의 노드를 리스트로 표현한 것이다.
주로 정점의 리스트 배열을 만들어 관계를 설정하며 노드들 간에 직접 연결이 되어있으면 해당 노드의 인덱스에 그 노드를 삽입해주면 된다.
즉, 1에는 2와 3이 직접 연결되어 있기 때문에 배열의 1번째 칸에 2와 3을 넣어준다.
-인접리스트의 장점
정점들의 연결 정보를 탐색할 때 O(n) 시간이면 가능하다.
필요한 만큼의 공간만 사용하기 때문에 공간의 낭비가 적다.
-인접리스트의 단점
특정 두 점이 연결되었는지 확인하려면 인접행렬에 비해 시간이 오래걸린다. (O(E) 시간 소요. E는 간선의 개수)
구현이 비교적 어렵다.
인접행렬
인접행렬은 그래프의 노드를 2차원 배열로 만든 것이다.
노드들 간에 직접 연결이 되어있으면 1을, 아니면 0을 넣어서 행렬을 완성시킨 것이다.
-인접행렬의 장점
2차원 배열 안에 모든 정점들의 간선 정보가 담겨있기 때문에 두 정점에 대한 연결 정보를 조회할 때 O(1) 의 시간복잡도면 가능하다.
인접리스트에 비해 구현이 쉽다.
-인접행렬의 단점
모든 정점에 대해 간선 정보를 대입해야 하므로 의 시간복잡도가 소요된다.
무조건 2차원 배열이 필요하기 때문에 필요 이상의 공간이 낭비된다.
그래프 용어
정점(vertex): 위치라는 개념. (node 라고도 부름)
간선(edge): 위치 간의 관계. 즉, 노드를 연결하는 선 (link, branch 라고도 부름)
인접 정점(adjacent vertex): 간선에 의 해 직접 연결된 정점
정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수
무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수의 2배
진입 차수(in-degree): 방향 그래프에서 외부에서 오는 간선의 수 (내차수 라고도 부름)
진출 차수(out-degree): 방향 그래픙에서 외부로 향하는 간선의 수 (외차수 라고도 부름)
방향 그래프에 있는 정점의 진입 차수 또는 진출 차수의 합 = 방향 그래프의 간선의 수(내차수 + 외차수)
경로 길이(path length): 경로를 구성하는 데 사용된 간선의 수
단순 경로(simple path): 경로 중에서 반복되는 정점이 없는 경우
사이클(cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경우
