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

그래프(Graph)

그래프는 노드와 간선의 집합으로 이루어진 자료구조이다.

객체 간의 관계를 선으로 연결하여 표현하는 형태로, 각 정점 간에는 부모-자식 관계가 없다.

너비 우선 탐색(BFS), 깊이 우선 탐색(DFS) 알고리즘에서 그래프를 순회하는 방식에서 사용한다.

 

그래프에서 사용하는 용어

• 노드/정점(Vertex): 데이터가 저장되는 기본 객체
• 간선(Edge): 정점을 연결하는 선
• 인접 정점: 간선에 의해 직접 연결된 노드로, 한 정점에서 간선을 한 번에 갈 수 있다면 해당 정점들은 인접하다고 할 수 있다.
• 단순 경로: 경로 중에서 반복되는 정점이 없는 경우

 

그래프 종류

무방향 그래프

모든 간선이 양방향인 그래프로, 방향이 없기 때문에 양쪽의 방향 모두 이동이 가능하다.

방향 그래프

간선들의 방향이 존재하는 그래프로, 방향을 나타내는 화살표로 표시하고 그 방향으로만 이동 가능하다.

가중치 그래프

각각의 간선이 가중치를 가진 그래프로, 노드를 이동할 때 드는 비용 등 추가적인 정보를 가진 그래프를 의미한다.

완전 그래프

모든 정점들이 인접한 그래프로, 그래프에 속해 있는 모든 정점이 서로 연결되어 있음을 의미한다.

N개의 정점이 있다면 모든 정점은 N-1개의 간선을 가진다.

연결 그래프

무방향 그래프에서 항상 경로가 존재하는 경우를 말하며, 모든 노드가 연결된 그래프를 의미한다.

비연결 그래프

무방향 그래프에서 특정 노드와 노드 사이에 경로가 존재하지 않는 경우를 말하며, 모든 노드가 연결되어 있지 않은 그래프를 의미한다.

사이클

단순 경로의 시작 노드와 종료 노드가 동일한 경우를 의미한다.

비순환 그래프

사이클이 없는 그래프를 의미한다.

 

그래프를 표현하는 방법

인접 행렬

• 2차원 배열로 정점과 간선을 표현하는 방식
• 두 노드를 연결하는 간선이 있으면 1, 없으면 0으로 표시
• 2차원 배열 안에 모든 노드의 간선 정보를 담기 때문에 두 노드에 대한 연결 정보를 조회할 때 O(1)의 시간 복잡도 소요
• 간선 정보를 삽입할 때 O(n^2)의 시간 복잡도 소요
• 인접 리스트에 비해 더 많은 메모리 공간 필요

인접 리스트

• 각 정점의 리스트는 헤더 노드를 가지고, 헤더 노드에 계속 정점을 연결하는 방식
• 필요한 정보만 저장하므로 메모리 절약
• 노드의 간선 정보를 탐색할 때 O(n)의 시간 복잡도 소요
• 인접 행렬에 비해 구현히 비교적 어려움

 

그래프와 트리의 차이

구분	그래프	트리
정의	노드와 간선의 조합으로 이루어진 자료구조	그래프의 한 종류로, 방향성이 있는 비순환 그래프
방향성	방향 그래프, 무방향 그래프	방향 그래프
사이클	가능	불가능
루트 노드	존재하지 않음	한 개의 루트 노드만 존재함
부모-자식 관계	존재하지 않음	존재함