(2024-2 자료구조반) 5. 그래프

권용훈·2025년 2월 15일

gbsw 재학생 부트캠프 - 2024 winter

gbsw 부트캠프 시리즈

목록 보기

17/32

지난 시간에는 데이터를 계층형태로 저장하는 트리를 알아보겠습니다.
이번 시간에는 데이터를 각각의 관계 형태로 저장하는 그래프를 알아보겠습니다.

1) 정의

데이터인 노드(Node)와, 그들을 연결하는 간선(Edge)으로 이루어진 자료구조입니다.

학교 수학시간에 배운 그래프(막대 그래프, 꺾은선 그래프)와는 다릅니다.

2) 그래프와 트리의 차이

그래프와 트리는 같은 점이 많기에, 차이점이 잘 보이지 않을 수도 있습니다.

그래프와 트리는 다음과 같은 차이점이 있습니다.

그래프	트리
노드와 간선으로 이루어져 있는 자료구조	그래프의 대표적인 한 종류.
유향 그래프와 무향 그래프가 있다.	무조건 유향 그래프이다.
사이클이 존재할 수 있다.	사이클이 존재할 수 없다.
루트 노드의 개념이 없다.	무조건 하나의 루트 노드가 존재한다.
부모, 자식의 개념이 없다.	부모, 자식, 리프 등의 개념이 있다.
DFS, BFS등의 방법으로 순회한다.	전위 순회, 중위 순회, 후위 순회 등이 방법으로 순회한다.
그래프에 따라 간선의 개수가 다르다.	노드의 개수가 N인 트리의 간선의 개수는 N-1개이다.

3) 그래프의 종류

간선의 종류에 따라 다음과 같이 분류할 수 있습니다.

(1) 무향 그래프

간선에 방향이 없는 그래프입니다.
이 경우, 모든 방향으로 간선을 지나갈 수 있습니다.

(A, B)와 (B, A)는 동일합니다.

정점 A와 B를 연결하는 간선을 (A, B)로 표기합니다.

(2) 유향 그래프

간선에 방향이 있는 그래프입니다.
이 경우, 한 방향으로만 간선을 지나갈 수 있습니다.

<A, B>와 <B, A>는 동일하지 않습니다.

정점 A에서 B로 연결된 유향 간선을 <A, B>로 표기합니다.

(3) 가중치 그래프

간선에 가중치가 있는 그래프입니다.
쉽게 설명하면, 간선으로 이동하는 데 드는 비용, 또는 간선의 길이입니다.

다음 그래프에서 (2, 5)의 가중치는 2이며,
정점3에서 5로 가는 경로의 최소 가중치는 3입니다.

(4) 연결 그래프

무향 그래프에서, 모든 정점쌍에 대해 항상 경로가 존재하는 그래프입니다.

(1)의 예시 사진은 연결 그래프입니다.

(5) 비연결 그래프

무향 그래프에서, 특정 정점쌍에 대해 경로가 존재하지 않는 그래프입니다.

다음 그래프에서, 정점3에서 6으로 가는 경로는 없습니다.

(6) 비순환 그래프

사이클이 없는 그래프입니다.

다음 그래프에서, 한 노드에서 출발해 특정 노드를 두 번 이상 지나지 않고 처음 노드로 돌아오는 경로는 없습니다.

(7) 완전 그래프

임의의 두 노드 A, B에 대해 (A, B)가 존재하는 그래프입니다.

무향 완전 그래프의 경우, 노드의 개수가 $N$ 일 때 정점의 개수는 $N(N-1)/2$ 입니다.

4) 그래프 구현

그래프는 크게 두 가지 방법으로 구현할 수 있습니다.

인접 행렬(2차원 배열)
인접 리스트(2차원 동적배열)

1번 방법은 구현이 간단하지만, 실행시간 및 변수의 크기가 커지기에 생략하겠습니다.

저희가 볼 방법은 2차원 동적배열입니다.

다음과 같은 배열을 선언하겠습니다.

$graph_n$ : n번 노드에서 이동할 수 있는 노드들

다음 그래프에서, $graph$ 의 상태는 다음과 같습니다.

$graph_0=\{1\}$
$graph_1=\{0,2,4\}$
$graph_2=\{1, 3, 5\}$
$graph_3=\{2\}$
$graph_4=\{1,5,6\}$
$graph_5=\{2,4\}$
$graph_6=\{4\}$

코드로 표현하면 다음과 같습니다.

#include <iostream>
#include <vector>
using namespace std;

// 최대 1000개의 노드를 저장할 수 있는 그래프
vector<int> graph[1000]{}; 

int main() {
	int n;cin >> n; // 간선의 개수

	// 간선의 정보를 입력받는다.
	for (int i = 0;i < n;i++) {

		int a, b;cin >> a >> b;

		graph[a].push_back(b); // a에서 b로 가는 간선 추가
		graph[b].push_back(a); // (무향 그래프일 경우) b에서 a로 가는 간선 추가

	}
}

5) 그래프 순회

그래프를 순회하는 대표적인 방법은 두 가지가 있습니다.

DFS(Depth-First-Search)
한 곳을 선택하여 끝까지 탐색한 후 다른 인접한 노드를 방문하는 방법입니다.
BFS(Breadth-First-Search)
시작 노드에서 가장 가까운 노드를 먼저 방문하는 방법입니다.

그림으로 보면 다음과 같습니다.

(출처: http://blog.hackerearth.com/wp-content/uploads/2015/05/dfsbfs_animation_final.gif)

DFS는 끝을 볼 때 까지 한 곳을 판 후, 끝을 보면 이전의 단계로 돌아가 다른 노드를 탐색합니다.

BFS는 물질이 확산하듯, 시작 노드에서 가장 가까운 노드 순서대로 방문합니다.

1260번 문제

무향 그래프가 주어지면, 그 그래프를 DFS한 결과와 BFS한 결과를 반환하는 문제입니다.

(1) DFS

다음과 같이 구현할 수 있습니다.

// current: 현재 노드
// visit: visit[i]가 true일 경우, 이미 방문한 노드
// graph: 2차원 동적배열로 구현한 그래프
void dfs(int current) {

	// 방문하였음을 알리기
	visit[current] = true;
	cout << current << ' ';

	// 현재 노드와 연결된 모든 노드 중
	for(int i : graph[current]) {
    
    	// 방문하지 않은 노드가 있다면 방문
		if (!visit[i])
			dfs(i);
	}
}

재귀함수를 사용하여 구현하였습니다.

실행을 하면, 현재 경로를 끝까지 파고든 후 다음 경로를 방문합니다.

(2) BFS

다음과 같이 구현할 수 있습니다.

// source: 시작 노드
// visit: visit[i]가 true일 경우, 이미 방문한 노드
// graph: 2차원 동적배열로 구현한 그래프
// q: 노드를 순서대로 방문하기 위한 큐, STL을 사용했습니다.
void bfs(int source) {
	queue<int> q;

	// 방문하였음을 알리기
	q.push(source);
	visit[source] = true;
	cout << source << ' ';

	while (!q.empty()) {
    	// 시작 노드와 가장 가까운 노드 중, 확산할 순서인 노드를 꺼냄
		int current = q.front();
		q.pop();
		
        // 현재 노드와 연결된 모든 노드 중
		for (int i : graph[current]) {
        
        	// 방문하지 않은 노드가 있다면 방문
			if (!visit[i]) {
				q.push(i);
				visit[i] = true;
				cout << i << ' ';
			}
		}
	}
}

자료구조인 큐를 사용하였습니다.

실행을 하면, 시작 노드와 가장 가까운 노드부터 방문을 합니다.

(3) 정답 코드

그래프의 dfs와 bfs를 구현하는 방법을 알았습니다.

문제의 정답 코드는 다음과 같습니다.

// made by biggrace681
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

vector<int> graph[1001]{}; // 그래프를 저장할 배열
bool visit[1001]{};		   // visit[i]=true라면, 이미 방문한 노드

// current: 현재 노드
void dfs(int current) {

	// 노드 방문
	visit[current] = true;
	cout << current << ' ';

	// 현재 노드와 연결된 모든 노드 중
	for (int i : graph[current]) {
		

		// 방문하지 않은 노드를 방문
		if (!visit[i])
			dfs(i);
	}
}

// source: 시작 노드
void bfs(int source) {

	// 방문 순서를 관리할 큐
	queue<int> q;

	// 노드 방문
	visit[source] = true;
	cout << source << ' ';
	q.push(source);

	while (!q.empty()) {

		// 시작 노드와 가장 가까운 노드 중, 확산할 순서인 노드
		int current = q.front();
		q.pop();

		// 현재 노드와 연결된 모든 노드 중
		for (int i : graph[current]) {

			// 방문하지 않은 노드를 방문
			if (!visit[i]) {
				visit[i] = true;
				cout << i << ' ';
				q.push(i);
			}
		}

	}
}

int main() {
	int n, m, v;cin >> n >> m >> v;

	for (int i = 0;i < m;i++) {

		int a, b; cin >> a >> b; // (a, b) 입력

		graph[a].push_back(b); // a에서 b로 가는 노드
		graph[b].push_back(a); // b에서 a로 가는 노드

	}

	// 정점이 여러 개면 번호가 작은 것을 먼저 방문하기 위해 정렬
	for (int i = 1;i <= 1000;i++)
		sort(graph[i].begin(), graph[i].end());

	dfs(v); // v번째 노드가 시작 노드, dfs 시작

	cout << '\n';

	fill(visit, visit + 1001, false); // visit배열 재활용

	bfs(v); // bfs 시작

}

과제

지금까지 2학년 1학기 과정인 자료구조를 알아보았습니다.

다음 시간에는 기타 유명한 자료구조를 알아보겠습니다.

권용훈

PS악귀.

이전 포스트

(2024-2 자료구조반) 4. 트리

다음 포스트