BFS DFS 구현하기

#include <string>
#include <vector>
#include <iostream>
#include <set>
#include <map>
#include <queue>
#include <stack>

using namespace std;

template <typename T>
struct Edge
{
	unsigned src;
	unsigned dst;
	T weight;
};

template <typename T>
class Graph
{
public:
	// N개의 정점으로 구성된 그래프
	Graph(unsigned N) : V(N) {}

	// 그래프의 정점 개수 반환
	auto vertices() const { return V; }
	
	// 전체 에지 리스트 반환
	auto& edges() const { reuturn edge_list; }

	// 정점 v에서 나가는 모든 에지를 반환
	auto edges(unsigned v) const
	{
		vector<Edge<T>> edges_from_v;
		for (auto& e : edge_list)
		{
			if (e.src == v)
				edges_from_v.emplace_back(e);
		}
		
		return edges_from_v;
	}

	// 엣지 추가
	void add_edge(Edge<T>&& e)
	{
		// 에지 양 끝 정점 ID가 유효한지 검사
		if (e.src >= 1 && e.src <= e.dst && e.dst >= 1 && e.dst <= V)
			edge_list.emplace_back(e);
		else
			cerr << "에러 : 유효 범위 벗어난 정점입니다. " << endl;
	}

	// 표준 출력 스트림 지원
	template <typename U>
	friend ostream& operator<< (ostream& os, const Graph<U>& G);

private:
	unsigned V;
	vector<Edge<T>> edge_list;

};

template<typename U>
ostream& operator<<(ostream& os, const Graph<U>& G)
{
	for (unsigned i = 1; i < G.vertices(); i++)
	{
		os << i << ":\t";
		auto edges = G.edges(i);
		for (auto& e : edges)
			os << "{" << e.dst << ": " << e.weight << "}, ";
		os << endl;
	}
	return os;
}

template <typename T>
auto breath_first_search(const Graph<T>& G, unsigned start)
{
	queue<unsigned> que;
	set<unsigned> visited;
	vector<unsigned> visit_order;
	que.push(start);

	while (!queue.empty())
	{
		auto current_vertex = queue.front();
		queue.pop();

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

			for (auto& e : G.edges(current_vertex))
			{
				if (visited.find(e.dst) == visited.end())
					que.push(e.dst);
			}
		}
	}
}

template<typename T>
auto depth_first_earch(const Graph<T>& G, unsigned start)
{
	stack<unsigned> stk;
	set<unsigned> visited;
	vector<unsigned> visit_order;
	stk.push(start);

	while (!stk.empty())
	{
		auto current_vertex = stk.top();
		stk.pop();

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

			for (auto& e : G.edges(current_vertex))
			{
				visited.insert(current_vertex);
				visit_order.push_back(current_vertex);

				if (visited.find(e.dst) == visited.end())
					stack.push(e.dst);
			}
		}
	}
}