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

junhok82·2020년 7월 20일
1

자료구조

목록 보기
4/4

그래프는 실생활에서 인터넷, 금융, 도로, 신경망, 소셜 네트워크 분석 등 광범위한 분야에서 활용되는 자료구조다. 그래프 이론을 통해서 우리가 알아야할 알고리즘은, 그래프의 기본 연산이라 할 수있는 깊이 우선 탐색(DFS, Depth-First-Search)와 너비 우선 탐색(BFS, Breadth-Fisrt-Search)부터 연결성분, 위상정렬, 최소신장트리(MST, Minimum Spanning Tree), 여러 가중치 그래프 등이 있다.


그래프 용어

그래프를 응용하여 해결하는 알고리즘에 있어서 중요한것은 용어와 그래프의 특징이다. 그 중에 먼저 용어를 알아보자.

정점(Vertex)과 간선(Edge)

그래프는 정점(Vertex)과 간선(Edge)의 집합으로 하나의 간선은 두 개의 정점을 연결한다. 즉 정점은 하나의 노드(node)라고 표현하고, 두개의 노드들을 잇는 선을 간선이라고 일컷는다.

방향 그래프 vs 무방향 그래프

간선에 방향이 있는 그래프를 방향 그래프(Directed Graph)라 하고, 간선에 방향이 없는 그래프를 무방향 그래프(Undiredcted Graph)라고 한다.

차수 (Degree)

위 그림에서 각 정점은 차수(Degree)를 가지고 있다. 차수는 해당 정점과 인접한 정점의 개수를 뜻한다. 단, 방향 그래프에서는 차수를 진입차수(In-degree)와 진출차수(Out-degree)로 구분된다. 즉 방향 그래프에서 정점 A는 진입 차수 1이고 진출차수는 2다. 반면 무방향 그래프에서 정점 A의 차수는 2다.

싸이클 (Cycle)

싸이클은 말 그대로 순환되는 경로를 말한다. 이 때, 경로란 출발점 u부터 v까지 가는 경로를 일컷는다. 위에서 보여준 예시는 모두 순환되는 그래프의 예이다. 즉, 시작 정점에서 다른 정점으로 이동했을때 결국 시작 정점으로 돌아오는 그래프다. 반면에 싸이클이 없는 그래프는 트리(Tree)라고 한다.

연결성분 (Connected Component)

줄여서 컴포넌트라고 부르곤한다. 컴포넌트는 그래프안의 모든 정점들이 이동가능한 상태를 말한다. 아래 그림에서는 [D][A,C,B]로 두 개의 컴포넌트를 가지고있다.

가중치 (Weighted)

가중치(Weighted) 그래프는 간선에 가중치가 부여된 그래프다. 가중치는 실제 두 정점의 거리가 될 수도있고, 두 정점을 지나는 시간이 될수도 있다. 때로는 음의 가중치도 존재하며 이러한 것들을 다루는 그리디 알고리즘과 DP가 존재한다. (다익스트라, 밸만포드, 플로이드)

부분그래프(Subgraph)

부분그래프(Subgraph)는 주어진 그래프의 정점과 간선의 집합으로 이루어진 그래프다. 위에서 언급한 트리(Tree)와 모든 정점들을 싸이클 없이 연결하는 그래프를 신장 트리 (Spanning Tree)라고 한다. 이는 최소 신장 트리 (MST, Minimum Spanning Tree)로 응용이 되는데, 간단히 싸이클 없이 연결하는 간선 중 가중치를 가장 적게 가지는 그래프를 말한다.

그래프 구현

그래프를 구현하는데 있어서 중요한 점은 '정점과 간선 처리를 어떻게 해줄 것인가'이다. 이를 표현하기 위해서 대표적으로 두가지 방법이 있다.

  1. 인접 행렬(Adjacency Matrix)
  2. 인접 리스트(Adjacency List)

인접 행렬

인접 행렬은 N개의 정점은 가진 그래프가 각각의 간선이 어디있는지 행렬로 표현하는 방법이다. 보통 정점이 1차원이면 2차원 행렬로 각 정점마다의 간선 정보를 표현할 수 있다. 가령 adj[i][j] 는 i에서 j로 가는 간선 정보를 알려준다.

인접 리스트

인접 리스트는 N개의 정점에 대해서 각각 하나의 연결리스트에 연결정보를 담아서 구현하는 방법이다.

profile
거북이

0개의 댓글