개발
[자료구조] 그래프
ash_
2024. 2. 1. 16:10
그래프란?
그래프는 정점(Vertext)와 간선(Edge)로 이루어진 자료구조이다.
트리는 그래프의 일종이라고 볼 수 있지만, 그래프는 트리와 달리 루트노드와 부모-자식 개념이 없으며, 정점마다 간선이 있을 수도 있고 없을 수도 있다.
그래프 용어
- 정점(Vertex) : 노드(node) 라고도 하며 정점에는 데이터가 저장된다. (0, 1, 2, 3)
- 간선(Edge) : 정점(노드)를 연결하는 선으로 link, branch 라고도 부른다.
- 인접 정점(adjacent Vertex) : 간선에 의해 직접 연결된 정점 (0과 2은 인접정점)
- 단순 경로(simple path) : 경로 중에서 반복되는 정점이 없는 경우. ( 0->3->2->1 은 단순경로 )
- 차수(degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 (0의 차수는 3)
- 진출 차수(in-degree) : 방향 그래프에서 외부로 향하는 간선의 수
- 진입 차수(out-degree) : 방향 그래프에서 외부에서 들어오는 간선의 수
- 경로 길이(path length) : 경로를 구성하는데 사용된 간선의 수
- 사이클(cycle) : 단순 경로의 시작 정점과 종료 정점이 동일한 경우
그래프의 종류
무방향 그래프
무방향 그래프는 두 정점을 연결하는 간선에 방향이 없는 그래프이다.
방향 그래프
방향 그래프는 두 정점을 연결하는 간선에 방향이 존재하는 그래프이다.
간선이 가리키는 방향으로만 이동할 수 있다.
가중치 그래프
가중치 그래프는 두 정점을 이동할 때, 비용이 드는 그래프이다.
완전 그래프
완전 그래프는 모든 정점이 간선으로 연결된 그래프이다.
그래프 구현 방법
인접행렬 방식
인접행렬은 그래프의 각 노드를 2차원 배열로 만든 것이다.
위처럼 2차원 배열로 만든 후, 인접 정점이라면 1, 아니면 0을 넣어준다.
장점
- 2차원 배열에 모든 정점의 간선 정보가 담겨있기 때문에 두 정점에 대한 연결을 조회할 때는 $O(1)$의 시간 복잡도를 가진다.
- 정점의 차수 는 O(N) 안에 알 수 있다 : 인접 배열의 i번 째 행 또는 열을 모두 더한다
- 인접 리스트에 비해 구현이 쉽다.
단점
- 모든 정점에 대해 간선 정보를 입력해야 하므로 인접 행렬을 생성하거나 모든 간선을 찾을 때에는할 때는 $O(n^2)$ 의 시간 복잡도가 소요된다.
- 어떤 노드에 인접한 노드들을 찾기 위해서는 모든 노드를 전부 순회해야 한다.
- 항상 2차원 배열이 필요하므로 필요 이상의 공간이 낭비된다.
인접리스트 방식
인접 리스트는 그래프의 노드들을 리스트로 표현한 것으로, 주로 정점에 인접한 노드들을 리스트 배열로 표현한다,
장점
- 어떤 노드에 인접한 노드를 쉽게 찾을 수 있다. $O(E)$ (E는 간선의 개수)
- 필요한 만큼 공간을 사용하기 때문에 인접 행렬에 비해 상대적으로 공간의 낭비가 적다.
단점
- 특정 두 정점이 연결되어 있는지 확인하기 위해서는 인접 행렬에 비해 시간이 오래 걸린다.
- 구현이 인접 행렬에 비해 어렵다.
그래프의 탐색
깊이 우선 탐색(DFS)
- 갈 수 있는 만큼 최대한 깊이 가고, 더 이상 갈 곳이 없다면 이전 정점으로 돌아가는 방식으로 그래프를 순회한다.
- 주로 재귀 호출과 스택을 사용해서 구현한다.
넓이 우선 탐색(BFS)
- 시작 정점을 방문한 후, 시작 정점에 인접한 모든 정점을 방문한다.
- 인접한 정점을 방문한 뒤, 다시 해당 정점의 인접한 정점을 방문하며 그래프를 순회한다.
- 주로 큐와 반복문을 사용해서 구현한다.
! 모든 간선에 가중치가 존재하지않거나 모든 간선의 가중치가 같은 경우, BFS 로 구한 경로는 최단 경로이다.
참고 레퍼런스
[Algorithm] 자료구조 그래프(Graph)란 무엇인가?