[0x18] 그래프

정점과 간선으로 이루어진 자료구조

 

차수 : 각 정점에 대해서 간선으로 연결된 이웃한 정점의 개수

방향 그래프 : 두 정점 사이에 진출차수(indegree)와 진입차수(outdegree)가 존재하는 그래프

무방향 그래프 : 두 정점 사이에 방향이 존재하지 않는 그래프

순환 그래프 : 사이클이 존재하는 그래프

비순환 그래프 : 사이클이 존재하지 않는 그래프

완전 그래프 : 모든 정점끼리 간선으로 연결된 그래프

연결 그래프 : 임의의 두 정점 사이에 경로가 항상 존재하는 그래프

단순 그래프 : 두 정점 사이의 간선이 1개 이하이고 루프가 존재하지 않는 그래프

 

그래프는 꼭 연결되어 있을 필요도 없고, 두 정점 사이의 간선이 반드시 1개 이하일 필요도 없으며 간선이 반드시 두 정점을 연결해야 할 필요도 없다.

 

그래프의 표현법

 

정점이 V개, 간선이 E개일 때,

 

인접 행렬 : 어떤 두 정점이 연결되어 있는지를 O(1)에 알 수 있다. 2차원 배열을 사용하므로 O(V²)의 공간을 필요로 한다.

어떤 정점에 연결되어 있는 모든 정점의 목록을 알아내고 싶을 때도 개수와 무관하게 O(V)의 시간복잡도를 가진다.

연결여부를 많이 확인할 때, 혹은 간선의 개수가 V²에 가까울 때 효율적이다.

 

인접 리스트 : O(V+E)의 공간을 필요로 한다.

특정 정점에 연결된 모든 정점들을 자주 확인할 때, 혹은 간선의 개수가 V²보다 훨씬 적을 때 효율적이다.

 

일반적인 그래프 문제에서 두 정점이 연결되어있는지를 반복적으로 확인해야 하는 경우는 잘 없다.

 

BFS

 

진행 순서

1. 시작하는 정점을 큐에 넣고 방문했다는 표시를 남긴다
2. 큐에서 정점을 꺼내어 그 정점과 연결된 모든 정점들에 대해 3번을 진행한다
3. 해당 정점을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입한다
4. 큐가 빌 때 까지 2번을 반복한다

 

모든 정점이 큐에 최대 한번씩 들어가므로 인접 리스트에서 O(V+E), 인접 행렬에서 O(V²)의 시간복잡도를 가진다.

 

// 연결 그래프에서의 순회
vector<int> adj[10];
bool vis[10];
void bfs() {
	queue<int> q;
	q.push(1);
	vis[1] = true;
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		cout << cur << ' ';
		for (auto& nxt : adj[cur]) {
			if (vis[nxt]) continue;
			q.push(nxt);
			vis[nxt] = true;
		}
	}
}

 

// 연결 그래프에서 1번 정점과의 거리
vector<int> adj[10];
int dist[10];
void bfs() {
	fill(dist, dist + 10, -1);
	queue<int> q;
	q.push(1);
	dist[1] = 0;
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		cout << cur << ' ';
		for (auto& nxt : adj[cur]) {
			if (dist[nxt] != -1) continue;
			q.push(nxt);
			dist[nxt] = dist[cur]+1;
		}
	}
}

 

// 연결 그래프가 아닐 때 순회
vector<int> adj[10];
bool vis[10];
int v = 9; // 정점의 수
void bfs() {
	queue<int> q;
	for (int i = 1; i <= v; ++i)
	{
		if (vis[i]) continue;
		q.push(1);
		vis[1] = true;
		while (!q.empty()) {
			int cur = q.front();
			q.pop();
			cout << cur << ' ';
			for (auto& nxt : adj[cur]) {
				if (vis[nxt]) continue;
				q.push(nxt);
				vis[nxt] = true;
			}
		}
	}
}

 

1926: 그림 문제를 해결할 때 사용한 방법을 그대로 가져오면 된다.

 

DFS

 

진행 순서

1. 시작하는 정점을 스택에 넣고 방문했다는 표시를 남긴다
2. 스택에서 정점을 꺼내어 그 정점과 연결된 모든 정점들에 대해 3번을 진행한다
3. 해당 정점을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문햤다는 표시를 남기고 해당 칸을 스택에 삽입한다
4. 스택이 빌 때 까지 2번을 반복한다

 

모든 정점이 스택에 최대 한번씩 들어가므로 인접 리스트에서 O(V+E), 인접 행렬에서 O(V²)의 시간복잡도를 가진다.

 

비재귀적으로 구현하는것은 bfs에서 큐를 스택으로 바꾸면 된다.

 

// 연결 그래프에서의 순회, 재귀
vector<int> adj[10];
bool vis[10];
void dfs(int cur) {
	vis[cur] = true;
	cout << cur << ' ';
	for (auto& nxt : adj[cur])
	{
		if (vis[nxt]) continue;
		dfs(nxt);
	}
}

 

스택 메모리의 제한이 별도로 작게 설정된 곳에서는 재귀 대신 스택을 써서 구현해야 한다.

 

비재귀 DFS는 순회를 잘 수행하지만 엄밀히 말해서 관념적으로 생각하는 DFS와 방문 순서가 다르다.

재귀 DFS와 방문순서를 같게 하려면 방문 전에 방문표시를 남기고 push를 수행해야 한다

// 연결 그래프에서의 순회, 비재귀 (재귀와 같은 방문순서)
vector<int> adj[10];
bool vis[10];
void dfs() {
	stack<int> s;
	s.push(1);
	while (!s.empty())
	{
		int cur = s.top();
		s.pop();
		if (vis[cur]) continue;
		vis[cur] = true;
		cout << cur << ' ';
		for (auto& nxt : adj[cur])
		{
			if (vis[nxt]) continue;
			s.push(nxt);
		}
	}
}

 

코딩테스트 레벨에서는 bfs대신 dfs를 써야하는 상황이 별로 없다.

 

연습 문제

 

11724: 연결 요소의 개수

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

vector<int> adj[1002];
bool vis[1002];
int v, e, ans;

int main(void)
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> v >> e;
	while (e--)
	{
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}

	for (int i = 1; i <= v; ++i)
	{
		if (vis[i]) continue;
		queue<int> q;
		q.push(i);
		vis[i] = true;
		while (!q.empty())
		{
			int cur = q.front();
			q.pop();
			for (auto& elem : adj[cur])
			{
				if (vis[elem]) continue;
				q.push(elem);
				vis[elem] = true;
			}
		}
		ans++;
	}
	cout << ans;

	return 0;
}

 

무방향 그래프이므로 양쪽에 push_back을 해주어야 한다.

 

1260: DFS와 BFS

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

vector<int> adj[1002];
bool bvis[1002];
bool dvis[1002];
int n, m, v;

void dfs(int s)
{
	dvis[s] = true;
	cout << s << ' ';
	for (auto& elem : adj[s])
	{
		if (dvis[elem]) continue;
		dfs(elem);
	}
}

void bfs(int& s)
{
	queue<int> q;
	q.push(s);
	bvis[s] = true;
	while (!q.empty())
	{
		int cur = q.front();
		q.pop();
		cout << cur << ' ';
		for (auto& elem : adj[cur])
		{
			if (bvis[elem]) continue;
			q.push(elem);
			bvis[elem] = true;
		}
	}
	cout << '\n';
}

int main(void)
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m >> v;
	while (m--)
	{
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	
	for (int i = 1; i <= n; ++i)
		sort(adj[i].begin(), adj[i].end());

	dfs(v);
	cout << '\n';
	bfs(v);

	return 0;
}

 

스택은 재귀방식으로 편하게 구현해봤다

 

기본 문제

 

2606: 바이러스

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

vector<int> adj[101];
bool vis[101];
int v, e, ans;

int main(void)
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> v >> e;
	while (e--)
	{
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}

	queue<int> q;
	q.push(1);
	vis[1] = true;
	while (!q.empty())
	{
		int cur = q.front();
		q.pop();
		for (auto& nxt : adj[cur])
		{
			if (vis[nxt]) continue;
			q.push(nxt);
			vis[nxt] = true;
			ans++;
		}
	}
	cout << ans;

	return 0;
}

 

기초적인 bfs 문제

 

5567: 결혼식

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

vector<int> adj[501];
int vis[501];
int v, e, ans;

void bfs(int st)
{
	fill(vis + 1, vis + v + 1, -1);
	queue<int> q;
	q.push(st);
	vis[st] = 0;
	while (!q.empty())
	{
		int cur = q.front();
		q.pop();
		for (auto& nxt : adj[cur])
		{
			if (vis[nxt] != -1) continue;
			vis[nxt] = vis[cur] + 1;
			q.push(nxt);
			if (vis[nxt] > 2) return;
			ans++;
		}
	}
}

int main(void)
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> v >> e;
	while (e--)
	{
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	bfs(1);
	cout << ans;

	return 0;
}

 

차수가 2 이하인 간선과 연결된 정점만 카운트

 

11403: 경로 찾기

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

int adj[101][101];
int ans[101][101];
int v;

void bfs(int& st)
{
	bool vis[101] = {};
	queue<int> q;
	q.push(st); // 순환할수도 있으므로 여기서 방문처리를 하지 않는다
	while (!q.empty())
	{
		int cur = q.front();
		q.pop();
		for (int i = 1; i <= v; ++i)
		{
			if (vis[i] && cur == i)
			{
				ans[st][i] = 1;
				continue;
			}
			if (adj[cur][i] && !vis[i])
			{
				q.push(i);
				vis[i] = true;
				ans[st][i] = 1;
			}
		}
	}
}

int main(void)
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> v;

	for (int i = 1; i <= v; ++i)
	{
		for (int j = 1; j <= v; ++j)
		{
			cin >> adj[i][j];
		}
	}

	for (int i = 1; i <= v; ++i) bfs(i);
	for (int i = 1; i <= v; ++i)
	{
		for (int j = 1; j <= v; ++j) cout << ans[i][j] << ' ';
		cout << '\n';
	}

	return 0;
}

 

2660: 회장뽑기

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

const int INF = 1e9;
int adj[51][51];
int v;

int main(void)
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> v;

	for (int i = 1; i <= v; ++i)
	{
		fill(adj[i] + 1, adj[i] + v + 1, INF);
		adj[i][i] = 0;
	}

	while (true)
	{
		int a, b;
		cin >> a >> b;
		if (a + b < 0) break;
		adj[a][b] = 1;
		adj[b][a] = 1;
	}

	for (int k = 1; k <= v; ++k)
	{
		for (int i = 1; i <= v; ++i)
		{
			for (int j = 1; j <= v; ++j)
			{
				adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
				adj[j][i] = adj[i][j];
			}
		}
	}

	map<int, vector<int>> m;
	for (int i = 1; i <= v; ++i)
	{
		int mx = 0;
		for (int j = 1; j <= v; ++j) mx = max(mx, adj[i][j]);
		m[mx].push_back(i);
	}

	auto& t = m.begin()->second;
	sort(t.begin(), t.end());
	cout << m.begin()->first << ' ' << t.size() << '\n';
	for (auto& i : t) cout << i << ' ';

	return 0;
}