[자료구조] 그래프(Graph): 인접행렬과 인접리스트

토끼는 개발개발·2021년 11월 4일

data structure

Data Structure

목록 보기

2/2

✏️ 그래프(Graph)

👉🏻 그래프(Graph)란 노드(Node)와 간선(Edge)으로 연결관계를 표현하는 자료구조이다. 노드는 정점(Vertex)라고 불리기도 한다.

노드(node): 정점 (vertex)이라고도 하며 데이터가 저장되는 그래프의 기본 원소
간선 (edge): 링크(link)라고도 하며 노드 간의 관계
인접 노드: (adjacent node): 하나의 노드에서 간선에 의해 직접 연결되어 있는 노드
차수(degree): 노드에 연결된 간선의 수
진입 차수(in-degree): 외부에서 오는 간선의 수
진출 차수(out-degree): 외부로 향하는 간선의 수
경로 (path): 간선을 따라갈 수 있는 길
경로의 길이 (length): 경로를 구성하는 데 사용된 간선의 수
단순 경로 (simple path): 경로 중에서 반복되는 간선이 없는 경로
사이클 (cycle): 시작 노드와 종료 노드가 같은 단순 경로

📌 그래프의 종류

👉🏻 그래프의 종류에는 무방향 그래프, 가중치가 있는 무방향 그래프, 가중치가 있는 유방향 그래프가 있다.

📌 그래프의 구현

👉🏻 그래프를 구현하는 방법에는 인접행렬(Adjacency Matrix)와 인접리스트(Adjacency List)가 있다.

인접행렬(Adjacency Matrix): 2차원 배열로 그래프의 연결 관계를 표현하는 방식
인접리스트(Adjacency List): 리스트로 그래프의 연결 관계를 표현하는 방식

인접행렬(Adjacency Matrix)

노드의 개수가 n이라면 n*n 형태의 2차원 배열로 그래프의 연결 관계를 표현한다.
인접 행렬에서 행과 열은 노드를 의미하며, 각각의 원소들은 노드 간의 간선을 나타낸다.
adj[i][j] : 노드 i에서 노드 j로 가는 간선이 있으면 1, 아니면 0

가중치가 없는 무방향 그래프
: 연결되어 있는 경우 행렬에서 1의 값을 가지고, 연결되지 않은 경우 0의 값을 가진다. 두 개의 노드에서 간선이 동시에 연결되어 있기 때문에 인접 행렬이 대칭적 구조를 가진다.

가중치가 있는 유방향 그래프는 행렬
: 행렬에서 각 간선의 가중치 값이 저장된다. 이 경우 가중치가 0인 것과 간선이 없는 것이 구별돼야 한다.

장점: 2차원 배열에 모든 노드들의 간선 정보가 있기 때문에, 두 노드를 연결하는 간선을 조회할 때 O(1) 시간복잡도를 가진다.
단점: 간선의 수와 무관하게 항상 n² 크기의 2차원 배열이 필요하므로 메모리 공간이 낭비된다.
그래프의 모든 간선의 수를 알아내려면 인접행렬 전체를 확인해야 하므로 O(n²)의 시간이 소요된다.