[알고리즘] 그래프 순회 문제

CS/알고리즘

[알고리즘] 그래프 순회 문제

nowkoes 2023. 6. 14. 00:00

<본 카테고리는 "코딩 테스트를 위한 자료 구조와 알고리즘 with C++을 기반으로 작성하였습니다>

그래프 탐색

개요

　그래프 탐색(graph traversal problem), 또는 그래프 순회 문제(graph search problem)는 그래프의 일련의 정점을 체계적으로 방문하는 문제를 의미한다. 주어진 그래프 G = <V, E>에서 특정 정점 s를 시작점으로 하여, 모든 정점 v ∈ V를 한 번씩 방문하는 것이 이 문제의 목표다. 이 과정에서 방문된 정점의 순서는 탐색 알고리즘에 따라 달라진다. 탐색은 주로 그래프의 구조를 이해하거나, 특정 경로를 찾는 등의 목적으로 사용된다. 이를 통해 네트워크 연결 상태, 최단 경로, 사이클 등 그래프의 다양한 특성을 분석할 수 있다.

　그래프 탐색은 다양한 응용 분야에서 중요한 역할을 수행한다. 예를 들어, 네트워크 라우팅, SNS에서 친구 추천, 웹 크롤러 등에서 그래프 탐색 알고리즘이 활용된다. 대표적인 탐색 방법으로는 깊이 우선 탐색, 너비 우선 탐색 등이 있다. 이러한 방법들은 그래프의 구조와 요구사항에 따라 선택되며, 각각의 방법은 그래프의 서로 다른 특성을 강조하고 이용한다.

너비 우선 탐색

　너비 우선 탐색(breadth-first search, BFS)은 시작 정점을 방문한 후에, 시작 정점에서 인접한 모든 정점들을 우선적으로 방문하는 방법이다. 이 방식을 계속 적용하면서 더 이상 방문하지 않은 정점이 없을 때까지 반복한다.

　다음과 같은 그래프에 대해 BFS 알고리즘을 적용하여 너비 우선 탐색의 동작에 대해 이해해 보자. 먼저 시작점인 1을 방문한다.

　그리고 인접한 2, 3, 4 중 하나의 노드에 방문한다. 이때 이전 정점과 같은 거리에 있는 정점들의 방문 순서는 임의로 결정해도 된다.

　그 후 5, 6, 7, 8, 그리고 9, 10, 11, 12 정점을 방문하여 전체 그래프를 순회하면 된다. 여기서 알 수 있는 사실은 BFS는 모든 정점에 대해 자식 정점을 손자 정점보다 먼저 방문한다는 점이다. 이를 큐에 저장하여 시작 정점과 가까운 정점을 멀리 있는 정점보다 먼저 방문하는 코드를 구현해 보도록 하겠다.

구현

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
using us = unsigned;

template <typename T>
struct edge
{
	us _src, _dst;
	T _weight;
};

template <class T>
class graph
{
	us _v;
	std::vector<edge<T>> _edges;

public:
	graph(us n) : _v(n)
	{

	}

	auto vertices() const
	{
		return _v;
	}

	auto& edges() const
	{
		return _edges;
	}

	auto edges(us v) const
	{
		std::vector<edge<T>> edges_from_v;

		for (const auto& e : _edges)
		{
			if (e._src == v)
				edges_from_v.push_back(e);
		}

		return edges_from_v;
	}

	void add_edge(edge<T>&& e)
	{
		if (e._src >= 1 && e._src <= _v && e._dst >= 1 && e._src <= _v)
			_edges.push_back(e);

		else
			std::cerr << "error: invalid range\n";
	}

	template <typename t>
	friend std::ostream& operator << (std::ostream& os, const graph<t>& g)
	{
		for (us i = 1; i < g.vertices(); ++i)
		{
			os << i << ":\t";

			auto edges = g.edges(i);

			for (const auto& e : edges)
				os << "{" << e._dst << ": " << e._weight << "}, ";
			os << "\n";
		}

		return os;
	}
};

　에지와 표현하는 edge 구조체, 그래프를 표현하는 graph 클래스를 선언하여 작성한다. 이에 대한 자세한 설명은 지난 그래프 게시글을 참조하자.

template <typename T>
auto bfs(const graph<T>& g, us start)
{
	std::queue<us> q;
	std::set<us> visited;
	std::vector<us> visit_order;

	q.push(start);

	while (!q.empty())
	{
		auto current = q.front();
		q.pop();

		if (visited.find(current) == visited.end())
		{
			visited.insert(current);
			visit_order.push_back(current);

			for (const auto& e : g.edges(current))
			{
				if (visited.find(e._dst) == visited.end())
					q.push(e._dst);
			}
		}
	}

	return visit_order

　BFS 알고리즘을 구현한 bfs() 함수다. 방문한 정점을 담을 visited, 방문 순서를 담을 visit_order를 초기화한다. 너비 우선 탐색은 탐색 순서를 관리하기 위해 큐 자료구조를 사용한다. 즉, BFS가 진행되는 동안, 먼저 추가된 정점이 먼저 탐색되어야 하므로 FIFO 구조가 필요하기 때문에 큐를 차용한다.

　find() 함수를 이용하여 현재 정점을 이전에 방문한 적이 있는지 확인하고, 방문한 적이 없다면, visited와 visit_order에 각각 값을 추가하고, 인접한 정점 중 방문하지 않은 정점이 있다면 큐에 추가하는 방식으로 구현하였다.

int main()
{
	graph<us> g(12);

	std::map<us, std::vector<std::pair<us, us>>> edge_map;

	edge_map[1] = { {2,0}, {3,0}, {4,0} };
	edge_map[2] = { {5,0}, {6,0} };
	edge_map[3] = { {1,0} };
	edge_map[4] = { {1,0}, {7,0}, {8,0} };
	edge_map[5] = { {2,0}, {9,0}, {10,0} };
	edge_map[6] = { {2,0} };
	edge_map[7] = { {11,0}, {12,0} };
	edge_map[8] = { {4,0} };
	edge_map[9] = { {5,0} };
	edge_map[10] = { {5,0} };
	edge_map[11] = { {7,0} };
	edge_map[12] = { {7,0} };

	for (const auto& i : edge_map)
	{
		for (const auto& j : i.second)
			g.add_edge(edge<us> { i.first, j.first, j.second});
	}

	std::cout << "[Input graph]\n";
	std::cout << g << "\n";

	auto bfs_visit_order = bfs(g, 1);
	std::cout << "[BFS]\n";

	for (const auto& v : bfs_visit_order)
		std::cout << v << "\n";
}

총합본

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
using us = unsigned;

template <typename T>
struct edge
{
	us _src, _dst;
	T _weight;
};

template <class T>
class graph
{
	us _v;
	std::vector<edge<T>> _edges;

public:
	graph(us n) : _v(n)
	{

	}

	auto vertices() const
	{
		return _v;
	}

	auto& edges() const
	{
		return _edges;
	}

	auto edges(us v) const
	{
		std::vector<edge<T>> edges_from_v;

		for (const auto& e : _edges)
		{
			if (e._src == v)
				edges_from_v.push_back(e);
		}

		return edges_from_v;
	}

	void add_edge(edge<T>&& e)
	{
		if (e._src >= 1 && e._src <= _v && e._dst >= 1 && e._src <= _v)
			_edges.push_back(e);

		else
			std::cerr << "error: invalid range\n";
	}

	template <typename t>
	friend std::ostream& operator << (std::ostream& os, const graph<t>& g)
	{
		for (us i = 1; i < g.vertices(); ++i)
		{
			os << i << ":\t";

			auto edges = g.edges(i);

			for (const auto& e : edges)
				os << "{" << e._dst << ": " << e._weight << "}, ";
			os << "\n";
		}

		return os;
	}
};

template <typename T>
auto bfs(const graph<T>& g, us start)
{
	std::queue<us> q;
	std::set<us> visited;
	std::vector<us> visit_order;

	q.push(start);

	while (!q.empty())
	{
		auto current = q.front();
		q.pop();

		if (visited.find(current) == visited.end())
		{
			visited.insert(current);
			visit_order.push_back(current);

			for (const auto& e : g.edges(current))
			{
				if (visited.find(e._dst) == visited.end())
					q.push(e._dst);
			}
		}
	}

	return visit_order;
}

int main()
{
	graph<us> g(12);

	std::map<us, std::vector<std::pair<us, us>>> edge_map;

	edge_map[1] = { {2,0}, {3,0}, {4,0} };
	edge_map[2] = { {5,0}, {6,0} };
	edge_map[3] = { {1,0} };
	edge_map[4] = { {1,0}, {7,0}, {8,0} };
	edge_map[5] = { {2,0}, {9,0}, {10,0} };
	edge_map[6] = { {2,0} };
	edge_map[7] = { {11,0}, {12,0} };
	edge_map[8] = { {4,0} };
	edge_map[9] = { {5,0} };
	edge_map[10] = { {5,0} };
	edge_map[11] = { {7,0} };
	edge_map[12] = { {7,0} };

	for (const auto& i : edge_map)
	{
		for (const auto& j : i.second)
			g.add_edge(edge<us> { i.first, j.first, j.second});
	}

	std::cout << "[Input graph]\n";
	std::cout << g << "\n";

	auto bfs_visit_order = bfs(g, 1);
	std::cout << "[BFS]\n";

	for (const auto& v : bfs_visit_order)
		std::cout << v << "\n";
}

깊이 우선 탐색

　깊이 우선 탐색(depth-first search, DFS)은 시작 정점에서 시작하여 특정 경로를 따라 가능한 멀리 있는 정점을 재귀적으로 먼저 방문하는 방식이다. 만약 더 방문할 정점이 없다면, 다른 경로를 찾아 다시 멀어지는 백트래킹(backtracking) 방식을 채용한다.

　먼저 시작 노드인 1을 방문한다.

　임의의 정점 2부터 그 끝인 정점 9까지 탐색을 한다.

　더 이상 내려갈 곳이 없으므로 다시 돌아와 10을 탐색한다.

　위와 같은 방식으로 모든 정점을 순회한다. DFS를 구현하는 방식은 BFS와 거의 비슷하지만, 큐 대신에 스택을 사용한다는 점이 다르다. 현재 정점과 인접한 정점들을 재귀적으로 이동하면서 방문할 때 사용해야 하기 때문에 후입선출의 구조인 스택이 적합하기 때문이다.

template <typename T>
auto dfs(const graph<T>& g, us start)
{
	std::stack<us> st;
	std::set<us> visited;
	std::vector<us> visit_order;
	st.push(start);

	while (!st.empty())
	{
		auto current = st.top();
		st.pop();

		if (visited.find(current) == visited.end())
		{
			visited.insert(current);
			visit_order.push_back(current);

			for (const auto& e : g.edges(current))
			{
				if (visited.find(e._dst) == visited.end())
					st.push(e._dst);
			}
		}
	}

	return visit_order;
}

　기본적인 그래프와 에지의 구현은 BFS와 동일하니 생략한다. 그리고 queue 자료구조가 stack으로 바뀐 것을 제외하고는 동일하게 구현하였다.

int main()
{
	graph<us> g(12);

	std::map<us, std::vector<std::pair<us, us>>> edge_map;

	edge_map[1] = { {2,0}, {3,0}, {4,0} };
	edge_map[2] = { {5,0}, {6,0} };
	edge_map[3] = { {1,0} };
	edge_map[4] = { {1,0}, {7,0}, {8,0} };
	edge_map[5] = { {2,0}, {9,0}, {10,0} };
	edge_map[6] = { {2,0} };
	edge_map[7] = { {11,0}, {12,0} };
	edge_map[8] = { {4,0} };
	edge_map[9] = { {5,0} };
	edge_map[10] = { {5,0} };
	edge_map[11] = { {7,0} };
	edge_map[12] = { {7,0} };

	for (const auto& i : edge_map)
	{
		for (const auto& j : i.second)
			g.add_edge(edge<us> { i.first, j.first, j.second});
	}

	std::cout << "[Input graph]\n";
	std::cout << g << "\n";

	auto dfs_visit_order = dfs(g, 1);
	std::cout << "[DFS]\n";

	for (const auto& v : dfs_visit_order)
		std::cout << v << "\n";
}

총합본

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
using us = unsigned;

template <typename T>
struct edge
{
	us _src, _dst;
	T _weight;
};

template <class T>
class graph
{
	us _v;
	std::vector<edge<T>> _edges;

public:
	graph(us n) : _v(n)
	{

	}

	auto vertices() const
	{
		return _v;
	}

	auto& edges() const
	{
		return _edges;
	}

	auto edges(us v) const
	{
		std::vector<edge<T>> edges_from_v;

		for (const auto& e : _edges)
		{
			if (e._src == v)
				edges_from_v.push_back(e);
		}

		return edges_from_v;
	}

	void add_edge(edge<T>&& e)
	{
		if (e._src >= 1 && e._src <= _v && e._dst >= 1 && e._src <= _v)
			_edges.push_back(e);

		else
			std::cerr << "error: invalid range\n";
	}

	template <typename t>
	friend std::ostream& operator << (std::ostream& os, const graph<t>& g)
	{
		for (us i = 1; i < g.vertices(); ++i)
		{
			os << i << ":\t";

			auto edges = g.edges(i);

			for (const auto& e : edges)
				os << "{" << e._dst << ": " << e._weight << "}, ";
			os << "\n";
		}

		return os;
	}
};

template <typename T>
auto create_graph()
{
	graph<T> g(12);

	std::map<us, std::vector<std::pair<us, T>>> edge_map;

	edge_map[1] = { {2,0}, {3,0}, {4,0} };
	edge_map[2] = { {5,0}, {6,0} };
	edge_map[3] = { {1,0} };
	edge_map[4] = { {1,0}, {7,0}, {8,0} };
	edge_map[5] = { {2,0}, {9,0}, {10,0} };
	edge_map[6] = { {2,0} };
	edge_map[7] = { {11,0}, {12,0} };
	edge_map[8] = { {4,0} };
	edge_map[9] = { {5,0} };
	edge_map[10] = { {5,0} };
	edge_map[11] = { {7,0} };
	edge_map[12] = { {7,0} };

	for (const auto& i : edge_map)
	{
		for (const auto& j : i.second)
			g.add_edge(edge<T> { i.first, j.first, j.second});
	}

	return g;
}

template <typename T>
auto dfs(const graph<T>& g, us start)
{
	std::stack<us> st;
	std::set<us> visited;
	std::vector<us> visit_order;
	st.push(start);

	while (!st.empty())
	{
		auto current = st.top();
		st.pop();

		if (visited.find(current) == visited.end())
		{
			visited.insert(current);
			visit_order.push_back(current);

			for (const auto& e : g.edges(current))
			{
				if (visited.find(e._dst) == visited.end())
					st.push(e._dst);
			}
		}
	}

	return visit_order;
}


int main()
{
	graph<us> g(12);

	std::map<us, std::vector<std::pair<us, us>>> edge_map;

	edge_map[1] = { {2,0}, {3,0}, {4,0} };
	edge_map[2] = { {5,0}, {6,0} };
	edge_map[3] = { {1,0} };
	edge_map[4] = { {1,0}, {7,0}, {8,0} };
	edge_map[5] = { {2,0}, {9,0}, {10,0} };
	edge_map[6] = { {2,0} };
	edge_map[7] = { {11,0}, {12,0} };
	edge_map[8] = { {4,0} };
	edge_map[9] = { {5,0} };
	edge_map[10] = { {5,0} };
	edge_map[11] = { {7,0} };
	edge_map[12] = { {7,0} };

	for (const auto& i : edge_map)
	{
		for (const auto& j : i.second)
			g.add_edge(edge<us> { i.first, j.first, j.second});
	}

	std::cout << "[Input graph]\n";
	std::cout << g << "\n";

	auto dfs_visit_order = dfs(g, 1);
	std::cout << "[DFS]\n";

	for (const auto& v : dfs_visit_order)
		std::cout << v << "\n";
}

요약

그래프 탐색 문제
1. 정의: 그래프에 있는 모든 정점들을 순회하는 문제
2. 종류
　a. BFS: queue 자료 구조를 이용해 인접한 정점부터 확인하는 방법
　b. DFS: stack 자료 구조를 이용해 가능한 멀리 있는 정점을 재귀적으로 확인하는 방법

저작자표시 비영리 변경금지

'CS > 알고리즘' 카테고리의 다른 글

[알고리즘] 다익스트라 최단 경로 알고리즘 (0)	2023.06.17
[알고리즘] 프림 알고리즘 (0)	2023.06.15
[알고리즘] 그리디 알고리즘 - 그래프 컬러링 (0)	2023.05.30
[알고리즘] 그리디 알고리즘 - 최소 신장 트리 문제 (2) (0)	2023.05.29
[알고리즘] 그리디 알고리즘 - 최소 신장 트리 문제 (1) (0)	2023.05.27

현재글[알고리즘] 그래프 순회 문제

개발일지