그래프

노드와 그 노드를 연결하는 간선을 모아 놓은 자료구조

즉, 연결된 객체 간의 관계를 표현하는 자료구조

관련 용어

• 정점(vertex) : 위치라는 개념. node라고도 부름
• 간선(edge) : 위치 간의 관계. 즉, 노드를 연결하는 선. link, branch라고도 부름
• 인접 정점 : 간선에 의해 직접 연결된 정점
• 차수 : 무방향 그래프에서 하나의 정점에 인접한 정점의 수
• 진입 차수(내차수) : 방향 그래프에서 외부에서 오는 간선의 수
• 진출 차수(외차수) : 방향 그래프에서 외부로 향하는 간선의 수
• 경로 길이 : 경로를 구성하는 데 사용된 간선의 수
• 단순 경로 : 반복되는 정점이 없는 경로 (한붓그리기)
• 사이클 : 단순 경로의 시작과 종료 정점이 동일한 경우

그래프 구현 방법

1. 인접 행렬(2차원 배열) 방식

그래프의 노드를 2차원 배열로 만든 것. 노드 간에 직접 연결이 되어있으면 1, 아니면 0을 넣어서 행렬을 완성시킨다.

2. 인접 리스트 방식

그래프의 노드를 리스트로 표현한 것. 정점의 리스트 배열을 만들어 관계를 설정하며, 노드들 간에 직접 연결이 되어 있으면 해당 노드의 인덱스에 그 노드를 삽입해 주면 된다.

장단점

	인접 행렬	인접 리스트
장점	- 2차원 배열 안에 모든 정점들의 간선 정보가 담겨있기 때문에 두 정점에 대한 연결 정보를 조회할 때 O(1)의 시간복잡도가 가능하다. - 인접리스트에 비해 구현이 쉽다.	- 정점들의 연결 정보를 탐색할 때 O(n)의 시간복잡도가 가능하다. - 필요한 만큼의 공간만 사용하기 때문에 공간 낭비가 적다.
단점	- 모든 정점의 간선 정보를 삽입해야 하므로 O(n^2)의 시간 복잡도가 소요된다. - 무조건 2차원 배열을 사용해서 필요 이상의 공간이 낭비된다.	- 특정 두 점이 연결되어 있는지 확인하려면 인접행렬에 비해 시간이 오래걸린다.O(E) (E는 간선의 개수) - 구현이 비교적 어렵다.

종류

무방향 그래프

방향 그래프

가중치 그래프 : 간선에 가중치(비용)가 할당된 그래프로, 두 정점을 이용할 때 비용이 든다.

연결 그래프 : 무방향 그래프의 모든 정점 쌍이 항상 경로가 있는 그래프

비연결 그래프 : 무방향 그래프에서 특정 정점 사이에 경로가 없는 그래프.

완전 그래프 : 그래프의 모든 정점이 서로 직접 연결되어 있다.

순환 그래프 : 단순 경로에서 시작 정점과 도착 정점이 동일한 그래프

비순환 그래프 : 사이클이 없는 그래프

관련 알고리즘

탐색 알고리즘 : BFS, DFS