그래프(Graph)

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

그래프로 출제되는 문제는 코테에서 간혹 등장하곤 한다 특히, 다익스트라나 조건에 맞는 경로들을 추출한 뒤 재탐색하여 최적해를 구하는 등의 문제들이 주를 이룬다. 그러나, 그래프라는 자료구조나 그래프 탐색에 사용되는 알고리즘을 숙달하지 않은 상태라면 문제를 건들다가 시간이 끝나버리는 불상사가 발생하기 쉽다.

그래프(Graph)란?

정점(Vertex)와 간선(Edge)로 이루어진 자료구조이다. 엣지의 방향 유무에 따라 단방향 그래프 / 유향 그래프(Directed Graph), 무(양)방향 그래프 / 무향 그래프(Undirected Graph)로 나눌 수 있다.

그래프에서 사용하는 용어

• 정점(Vertex) : 노드(Node)라고도 부를 수 있으며 데이터가 저장되는 곳이다.
• 간선(Edge) : 링크(Arcs)라고도 부를 수 있고 노드 간의 관계를 나타낸다.
• 가중치(Weight) : 엣지에 표시된 숫자를 말한다. 그래프에 가중치가 없으면 모두 동일하다고 보면 되고 일반적으로 경로 산출 시 비용이나 우선순위 표현에 사용된다.
• 차수(Degree) : 하나의 노드에 인접한 엣지의 개수이다. 진출 차수와 진입 차수를 더하면 차수의 값과 동일하다.
• 진출 차수(Out-Degree) : Directed Graph에서 한 노드에서 외부로 나가는 엣지의 개수이다.
• 진입 차수(In-Degree) : Directed Graph에서 외부로부터 한 노드로 들어오는 엣지의 개수이다.
• 경로(Path) : 노드에서 노드로 이동할 수 있는 경로를 의미한다. Edge의 조합에 따라 여러 개 존재할 수 있다.
• 단순 경로(Simple Path) : 경로에 존재하는 노드들이 중복하여 등장하지 않는 경로를 의미한다.
• 사이클(Cycle) : 경로를 따라가 출발지점으로 돌아올 수 있는 경우를 말한다. 노드의 중복이 없으면 Path 처럼 Simple Cycle이라 부른다.
• 비순환 그래프(Acylic Graph) : 그래프에 Cycle이 존재하지 않는 Graph를 의미한다.
• 연결된 그래프(Connected Graph) : 모든 노드들을 하나의 경로로 이을 수 있는 그래프를 의미한다.

• 포레스트(Forest) : Acyclic, Undirected 조건을 만족하는 Graph를 의미한다.
• 트리(Tree) : Forest 중 Connected 조건을 만족하는 Graph를 의미한다.
• 대그(DAG, Directed Acyclic Graph) : Tree가 Undirected, Acyclic, Connected를 만족하는 그래프라면 DAG는 Directed, Acyclic, Connected를 만족하는 그래프다.

그래프의 표현 방법

그래프를 코드로 표현하기 위해 특정 자료구조로 변환해야 한다. 보통 인접 행렬방식이나 인접 리스트 두 가지 방식으로 나뉜다.

인접 행렬 방식

그래프를 행렬로 표현할 수 있음은 중고등학교 수학시간에 배웠다. 이걸 컴퓨터로 표현하면 이차원 배열로 가능하다.

장점

• 직관적이고 쉽게 구현할 수 있음
• 2차원 배열 내에 모든 Edge 정보를 저장해 두 점의 연결 정보 확인 시 O(1)에 가능

단점

• 불필효한 정보를 저장하게 되어 그래프의 크기가 커지면 메모리 요구량도 증가
• 모든 노드에 대한 Edge 정보를 저장해야 하므로 제작시 O($V^2$)가 소요됨
• 공간복잡도 또한 무조건 O($V^2$)가 소요됨

인접 리스트 방식

각 정점에서 갈 수 있는 노드만을 저장하는 방식이다. 컴퓨터로는 list 등을 원소로 갖는 Map이나 Dictionary 형태로 구현한다. 리스트 말고도 연결리스트로 구현할 수 있다.

장점

• 노드 간 연결 정보만을 저장하므로 제작 시 O($V$)에 가능
• 연결되지 않은 경우를 저장하지 않기 때문에 공간의 낭비가 적다.

단점

• 특정한 두 노드의 연결 정보 확인 시 노드의 차수가 $d$라면 O($d$)만큼 소요되어 O(1)보다 오래 걸림
• 연결리스트로 구현할 시 난이도가 급상승

인접 행렬 vs 인접 리스트

• 노드보다 엣지의 개수가 많으면(=Dense Graph) 인접 행렬이 유리하다. 이유는 전체 공간을 $V^2$라고 하면 연결 정보가 많아 데이터가 차지하는 비중이 많기 때문
• 노드보다 엣지의 개수가 적으면(=Sparse Graph) 인접 리스트가 유리하다. 전체 공간을 $V^2$이라 할 때 연결 정보가 적어 $V^2$를 고정적으로 저장하는 인접 행렬 방식의 경우 공간 낭비가 심해지기 때문