그래프 Graph
그래프는 정점(node)과 간선(edge)으로 이루어진 자료구조이다.
조금 더 구체적으로 말하면 각 정점(데이터)들의 관계(연결)를 나타낸 것으로 이해하면 된다.
비선형 자료구조로, 트리도 그래프 중 하나에 속한다.
그래프 용어
- 정점(node) : vertex 라고도 하며 정점에는 데이터가 저장된다.(0,1,2,3)
- 간선(edge) : 링크(arcs) 라고도 하며 노드간의 관계를 나타낸다.
- 인접정점(adjacent node) : 간선에 의해 연결된 정점(위 그림에서 정점 0과 정점 1은 인접 정점)
- 차수(degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수(정점 0의 차수는 3)
- 진출 차수(out-degree) : 방향그래프에서 사용되는 용어로 한 노드에서 외부로 향하는 간선의 수
- 진입 차수(in-degree) : 방향그래프에서 사용되는 용어로 외부 노드에서 들어오는 간선의 수
그래프 종류
그래프는 방향성을 띄고 있는지에 따라 방향 그래프와 무방향 그래프로 나뉜다.
위 그림에서 왼쪽은 방향그래프, 오른쪽은 무방향 그래프이다.
- 무방향 그래프 : 노드를 연결하는 간선에 방향이 없는 그래프
- 방향 그래프 : 간선에 방향이 존재하는 그래프로써 해당 방향으로만 이동할 수 있다.
- 가중치 그래프 : 노드를 이동할 때 지정한 비용이 드는 그래프
- 완전 그래프 : 모든 노드가 서로 연결되어있는 그래프
그래프 구현 방법
그래프를 구현하는 방법은 크게 두가지가 있다.
- 인접 행렬(Adjacency Matrix)
- 연결 리스트(Linked List)
1. 인접 행렬(Adjacency Matrix)
그래프의 노드를 2차원 배열로 나타낸 것이다. 해당 노드가 다른 노드에 연결되어있으면 1, 연결되어있지 않으면 0으로 나타낸다.
장점
- 2차원 배열 안에 모든 노드들의 정보를 담기 때문에 배열의 위치를 확인하면 두 점에 대한 연결 정보를 조회할 수 있다.
- 즉, 시간 복잡도가 낮다.(O(1))
- 구현이 상대적으로 간편하다.
단점
- 모든 노드에 대한 정보를 담아야 하기에 O(N^2)의 시간복잡도가 소요된다.
- 무조건 2차원 배열이 필요하기에 필요 이상의 공간을 차지한다.
2. 연결 리스트(Linked List)
그래프의 노드들을 리스트로 나타낸 것이다.
장점
- 노드들의 연결 정보를 탐색할때 O(N)의 시간복잡도
- 공간을 적게 차지한다.
단점
- 특정 두 점이 연결되어있는지 확인하기가 까다로움
- 구현이 상대적으로 복잡하다.
참고 자료
성장하는 developer