그래프, 트리, DFS C++

개요

그래프

정점과 정점사이의 상관관계를 나타내는 자료구조 노드와 간선으로 이루어져 있다.

1. 그래프의 방향

그래프는 방향이 있는 그래프와 방향이 없는 그래프로 나뉘어 진다. (양방향과 단방향)

2. 가중치

각 노드간 간선에 가중치가 있을 수 있다. (거리 등)

단방향, 각 간선에 가중치가 있는 그래프

 

3. 트리

그래프의 한 종류로 LEVEL이 설정되어 있는 그래프이다. LEVEL 0에 ROOT 노드가 있으며, 하위 노드는 자식이 된다. 반대로 자식 입장에서 ROOT 노드는 부모 노드이며, 자식간의 관계는 형제 노드가 된다.

트리 예시

트리의 특징

1. 방향 그래프만 존재
2. 루트 노드가 한개만 존재
3. 계층 형식으로 비순환 그래프

4. 인접 행렬

위 트리 노드를 인접 행렬로 표현하면 아래와 같이 표현할 수 있다.

노드	1	2	3	4	5
1	0	1	0	0	1
2	0	0	1	1	0
3	0	0	0	0	0
4	0	0	0	0	0
5	0	0	0	0	0

 

출발지 -> 도착지로 갈 수 있을 경우(연결되어 있을 경우)를 2차배열 형태로 나타낸다.

행을 출발지의 index, 열을 도착지의 index로 1에서 2로 갈 수 있다면 첫번째 행의 2번 칼럼에 체크를 해준다.

 

인접 행렬의 장점

1. 모든 노드간의 연결 여부 파악이 쉽다
2. 조회가 빠르다
3. 가중치를 넣을 수 있다.
4. 노드를 작은 순 or 큰 순으로 접근하는데 추가적인 연산 작업이 없어도 된다.

 

단점

1. 메모리 낭비가 있을 수 있다. (배열의 범위를 보고 사용 여부를 결정)

 

5. 인접 리스트

위 트리 노드를 인접 리스트로 표현하면 아래와 같이 표현할 수 있다.

노드	1	2	3	4	5
요소	2, 5	3, 4	-	-	-

 

구현할 경우 동일하게 2차 배열이지만 연결되지 않은 부분은 생략할 수 있다는 장점이 있다.

한 노드와 연결되어 있는 노드를 순회하거나 전체 탐색이 필요한 경우 유용하게 사용할 수 있다.

 

장점

1. 간선 정보 만큼만 메모리를 사용한다.

 

단점

1. 간선 개수만큼 조회 시간이 걸릴 수 있다.
2. 노드를 작은 순 or 큰 순으로 접근하는데 추가적인 정렬 연산이 필요하다.

 

6. DFS

DFS : Depth First Search, 깊이 우선 탐색

그래프에서 이루어지는 백트래킹 기법, 모든 노드를 확인하는 그래프 탐색방법 중에 하나

깊이를 우선으로 재귀를 실행한다.

 

DFS는 기본적으로 방문처리를 해 주어야 무한 루프가 발생하지 않는다.

 

방문 처리 후 재귀를 실행하고 방문 정보를 복구해 주지 않으면 모든 노드를 탐색하는 경우의 수 하나만 보는 것

방문 처리 후 재귀를 실행하고 방문 정보를 복구해 주면 모든 노드를 탐색하는 다른 경우의 수도 볼 것

 

종료조건 작성은 해도 되고 안해도 된다.

종료 조건을 작성하면 모든 노드를 방문하지 않고 끝나게 되고

종료 조건을 작성하지 않으면 모든 노드를 완전탐색 하게 된다.

 

 

예제

1. 인접 행렬 만들기

노드가 5개인 인접 행렬을 만들어 보자, 각 노드를 인덱스로 접근하기 편하기 위해 노드 + 1개의 행과 열을 만들어 준다. (혹은 더 크게 만들어 줘도 된다.)

 

코드

#include <iostream>

using namespace std;

int mat[10][10]; // 최대 10 * 10 크기, 9개 노드까지 들어올 수 있다.
int n, m;

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int from, to;
		cin >> from >> to;
		mat[from][to] = 1;
	}
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= n; j++) {
			cout << mat[i][j] << " ";
		}
		cout << "\n";
	}
}

 

입력

5 4
1 2
1 5
2 3
2 4

 

출력

0 0 0 0 0 0
0 0 1 0 0 1
0 0 0 1 1 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

 

2. 인접 리스트 만들기

코드

#include <iostream>
#include <vector>

using namespace std;

vector<int>v[10];
int n, m;

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int from, to;
		cin >> from >> to;
		v[from].push_back(to);
	}
	for (int i = 1; i <= n; i++) {
		cout << "노드 " << i << "의 자식들 : ";
		for (int j = 0; j < v[i].size(); j++) {
			cout << v[i][j] << " ";
		}
		cout << "\n";
	}
}

 

입력

5 4
1 2
1 5
2 3
2 4

 

출력

노드 1의 자식들 : 2 5
노드 2의 자식들 : 3 4
노드 3의 자식들 :
노드 4의 자식들 :
노드 5의 자식들 :

 

3. DFS

1. 특정 노드부터 시작하여 깊이를 기준으로 완전 탐색하기

예제용 그래프

 

코드

#include <iostream>
#include <vector>

using namespace std;

vector<int> lst[10];
vector<int> v(10, 0);
int n, m, s;

void dfs(int now) {
	for (int i = 0; i < lst[now].size(); i++) {
		int next = lst[now][i];
		if (!v[next]) {
			cout << next << " ";
			v[next] = 1;
			dfs(next);
		}
	}
}

int main() {
	cin >> n >> m >> s;
	for (int i = 0; i < m; i++) {
		int from, to;
		cin >> from >> to;
		lst[from] .push_back(to);
	}
	v[s] = 1;
	cout << s << " ";
	dfs(s);
}

 

입력

4 5 1 // 노드의 수, 간선의 수, 시작 노드
1 2
2 3
2 4
3 4
4 1

 

출력

1 2 3 4

 

1에서 부터 DFS를 시작한다면 1 > 2 > 3 > 4 순으로 그래프를 탐색하게 된다.

 

입력

4 5 2 // 노드의 수, 간선의 수, 시작 노드
1 2
2 3
2 4
3 4
4 1

 

출력

2 3 4 1

 

2에서 부터 DFS를 시작한다면 2 > 3 > 4 > 1 순으로 그래프를 탐색하게 된다.