그래프 Graph

게시 2024/02/11 업데이트 2024/02/13

Graph

By JeongJongMun 9 분읽는 시간

본 글은 제 개인적인 공부를 위해 작성한 글입니다. 틀린 내용이 있다면 언제든지 피드백을 주시면 감사하겠습니다. 참고로만 활용해주시길 바랍니다.

개요

그래프 Graph란 노드 Node와 간선 Edge으로 연결 관계를 표현하는 자료구조이다.

그래프 용어

노드 Node

정점(Vertex)이라고도 불림
노드는 무엇이든 표시 할 수 있다. 날씨, 배우 영화, 단백질이 될 수도 있다.

간선 Edge

원하는 만큼 노드를 가질 수 있지만, 노드를 연결할 수 있다.
에지(노드 간 연결선)를 통해 두 노드를 연결하고 두 노드 간에는 관계가 있음을 알 수 있다.

아크 Arc

$\approx$ 방향성 에지 Directed Edge
에지에 방향 화살표를 추가하면 그래프에 방향성이 생긴다.
노드 간의 관계는 에지와 화살표의 방향으로 정해진다.

인접 노드 Adjacent Node

하나의 노드에서 간선에 의해 직접 연결되어 있는 노드

차수 Degree

노드에 연결된 간선의 수

진입 차수 In-Degree

외부에서 오는 간선의 수

진출 차수 Out-Degree

외부로 향하는 간선의 수

경로 Path

간선을 따라갈 수 있는 길

경로의 길이 Length

경로를 구성하는 데 사용된 간선의 수

단순 경로 Simple Path

경로 중에서 반복되는 간선이 없는 경로

사이클 Cycle

시작 노드와 종료 노드가 같은 단순 경로

밀집 그래프에서의 에지 개수

무향 그래프
- $n(n-1)/2$
유향 그래프
- $n(n-1)$
결국 둘 다 $O(n^2)$

그래프의 종류

무방향 그래프, 가중치가 있는 무방향 그래프, 가중치가 있는 유방향 그래프가 있다.

그래프의 구현

	인접 행렬	인접 리스트
구현 난이도	쉬움	어려움
구현 방법	이차원 배열	연결 리스트
간선(u, v) 검색	$O(1)$	$O(Degree(v))$
정점(v)의 차수 계산	$O(n)$	$O(Degree(v))$
전체 정점 탐색	$O(n^2)$	$O(e)$
메모리	$n^2$	$n+e$

상황에 따라 최선의 방법을 선택하자.

정점의 개수가 적은 희소 그래프에서는 인접 리스트가 유리할 수 있고, 모든 정점 간에 간선이 존재하는 완전 그래프에서는 인접 행렬이 유리할 수 있다.

인접 행렬 Adjacency Matrix

이차원 배열로 그래프의 연결 관계를 표현하는 방식
인접 행렬을 adj[][]라고 한다면 adj[i][j]에 대해서 다음과 같이 정의한다.

$adj[i][j]$: 노드 $i$에서 노드 $j$로 가는 간선이 있으면 $1$, 아니면 $0$
$cf)$ 만약 간선에 가중치가 있는 그래프라면 1 대신에 가중치의 값을 직접 넣어주는 방식으로 구현할 수도 있다.
예시 방향이 있는 유향 그래프를 인접 행렬로 구현
만약 무향 그래프라면 대각 성분을 기준으로 대칭인 성질을 가지게 된다.
장점
- 구현이 쉬움
- 노드 $i$와 노드 $j$가 연결되어 있는지 확인하고 싶을 때, $adj[i][j]$가 1인지 0인지만 확인하면 되기에 $O(1)$의 시간복잡도를 가진다.
단점
- 전체 노드의 개수를 $V$, 간선의 개수를 $E$라고 한다면, 노드 $i$에 연결된 모든 노드들에 방문해보고 싶은 경우 $adj[i][1]$부터 $adj[i][V]$까지 모두 확인해보아야 하기에 $O(V)$의 시간복잡도를 가진다.
- 노드의 개수에 비해 간선의 개수가 훨씬 적은 그래프일 때, 비효율적이다. 2개의 간선을 조사하기 위해 1억 개의 노드를 검사할 수도 있다.

구현

  
# 무향 그래프를 인접 행렬로 구현하는 간단한 코드
# 2차원 리스트로 인접 행렬 표현
# 1. 노드의 개수, 간선의 개수
# 2. 각 간선의 양 끝 노드
# 순으로 주어진다 가정

node, edge = map(int, input().split())
graph = [[0] * (node + 1) for _ in range(node + 1)]
for i in range(edge):
    a, b = map(int, input().split())
    graph[a][b] = graph[b][a] = 1

print(*graph, sep='\n')

'''
4 5
1 2
1 3
1 4
2 3
3 4
'''

  
#include <bits/stdc++.h>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	int node, edge; cin >> node >> edge;
	int adj[100][100];

	memset(adj, 0, sizeof(adj));

	for (int i = 0; i < edge; ++i) {
		int u, v; cin >> u >> v;
		adj[u][v] = adj[v][u] = 1;
	}

	for (int i = 0; i < node; ++i) {
		for (int j = 0; j < node; ++j) {
			cout << adj[i][j] << " ";
		}
		cout << "\n";
	}

	return 0;
}

인접 리스트 Adjacency List

그래프의 연결 관계를 연결 리스트로 표현하는 방식
정점의 개수 만큼 인접 리스트가 존재하며, 각각의 인접 리스트에는 인접한 정점 정보가 저장
그래프는 각 인접 리스트에 대한 포인터를 가진다.
무방향 그래프의 경우 간선이 추가될 때, 각각의 정점의 인접리스트에 반대편 정점을 추가해야 한다.

예시
장점
- 존재하는 간선만 관리하면 되므로 메모리 사용 측면에서 효율적이다.
- 그래프의 모든 간선 수를 알아내려면 각 정점의 헤더 노드부터 모든 인접리스트를 탐색해야 하므로 $O(n+e)$의 시간이 소요된다.
단점
- 두 정점을 연결하는 간선을 조회하거나 정점의 차수를 알기 위해서는 정점의 인접 리스트를 탐색해야 하므로 정점의 차수만큼의 시간이 필요하다. $O(Degree(v))$

구현

  
# 인접 리스트를 사용한 간단한 무방향 그래프 예제
node, edge = map(int, input().split())
graph = [[] for _ in range(node+1)]
for i in range(edge):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

print(*graph, sep='\n')
'''
4 5
1 2
1 3
1 4
2 3
3 4
'''

  
#include <bits/stdc++.h>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	int node, edge; cin >> node >> edge;
	vector<int> adj[100];
	for (int i = 0; i < edge; ++i) {
		int u, v; cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	for (int i = 0; i <= node; ++i) {
		cout << i << " -> ";
		for (auto j : adj[i]) {
			cout << j << " ";
		}
		cout << endl;
	}


	return 0;
}

참고

Algorithm, Graph

Algorithm Graph