[자료구조] 그래프

그래프란?

그래프는 정점(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을 넣어준다.

 

장점

1. 2차원 배열에 모든 정점의 간선 정보가 담겨있기 때문에 두 정점에 대한 연결을 조회할 때는 $O(1)$의 시간 복잡도를 가진다.
2. 정점의 차수 는 O(N) 안에 알 수 있다 : 인접 배열의 i번 째 행 또는 열을 모두 더한다
3. 인접 리스트에 비해 구현이 쉽다.

단점

1. 모든 정점에 대해 간선 정보를 입력해야 하므로 인접 행렬을 생성하거나 모든 간선을 찾을 때에는할 때는 $O(n^2)$ 의 시간 복잡도가 소요된다.
2. 어떤 노드에 인접한 노드들을 찾기 위해서는 모든 노드를 전부 순회해야 한다.
3. 항상 2차원 배열이 필요하므로 필요 이상의 공간이 낭비된다.

 

인접리스트 방식

인접 리스트는 그래프의 노드들을 리스트로 표현한 것으로, 주로 정점에 인접한 노드들을 리스트 배열로 표현한다,

 

장점

1. 어떤 노드에 인접한 노드를 쉽게 찾을 수 있다. $O(E)$ (E는 간선의 개수)
2. 필요한 만큼 공간을 사용하기 때문에 인접 행렬에 비해 상대적으로 공간의 낭비가 적다.

단점

1. 특정 두 정점이 연결되어 있는지 확인하기 위해서는 인접 행렬에 비해 시간이 오래 걸린다.
2. 구현이 인접 행렬에 비해 어렵다.

그래프의 탐색

깊이 우선 탐색(DFS)

• 갈 수 있는 만큼 최대한 깊이 가고, 더 이상 갈 곳이 없다면 이전 정점으로 돌아가는 방식으로 그래프를 순회한다.
• 주로 재귀 호출과 스택을 사용해서 구현한다.

넓이 우선 탐색(BFS)

• 시작 정점을 방문한 후, 시작 정점에 인접한 모든 정점을 방문한다.
• 인접한 정점을 방문한 뒤, 다시 해당 정점의 인접한 정점을 방문하며 그래프를 순회한다.
• 주로 큐와 반복문을 사용해서 구현한다.

 

! 모든 간선에 가중치가 존재하지않거나 모든 간선의 가중치가 같은 경우, BFS 로 구한 경로는 최단 경로이다.

 

 

 

---

 

참고 레퍼런스

그래프(Graph) 개념정리 (자료구조)

[자료구조] 그래프(Graph)란

[Algorithm] 자료구조 그래프(Graph)란 무엇인가?

[자료구조] 그래프(Graph) 개념 정리

[그래프] 인접 행렬과 인접 리스트