# Graph Algorithm - DFS

thewoowon·2022년 3월 2일
0

## Algorithm

목록 보기
2/10

안녕하세요. 우웝입니다.

깊이 우선 탐색에 대해 코드를 작성하고 분석하겠습니다.

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

using namespace std;

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

template <typename T>
class  Graph
{
public:
Graph(unsigned N) : V(N) {}

auto vertices() const { return V; }

auto& edges() const { return edge_list; }

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;
}
{
// 에지 양 끝 정점 ID가 유효한지 검사
if (e.src >= 1 && e.src <= V && 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 create_reference_graph()
{
Graph<T> G(9);

map<unsigned, vector<pair<unsigned, T>>> edge_map;
edge_map[1] = { {2,0},{5,0} };
edge_map[2] = { {1,0},{5,0},{4,0} };
edge_map[3] = { {4,0},{7,0} };
edge_map[4] = { {2,0},{3,0},{5,0},{6,0},{8,0} };
edge_map[5] = { {1,0},{2,0},{4,0},{8,0} };
edge_map[6] = { {4,0},{7,0},{8,0} };
edge_map[7] = { {3,0},{6,0} };
edge_map[8] = { {4,0},{5,0},{6,0} };

for (auto& i : edge_map)
for (auto& j : i.second)

return G;
}

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

while (!stack.empty())
{
auto current_vertax = stack.top();
stack.pop();

// 현재 정점을 이전에 방문하지 않았다면
if (visited.find(current_vertax) == visited.end())
{
visited.insert(current_vertax);
visit_order.push_back(current_vertax);

for (auto& e : G.edges(current_vertax))
{
//인접한 정점 중애서 방문하지 않은 정점이 있다면 스택에 추가
if (visited.find(e.dst) == visited.end())
{
stack.push(e.dst);
}
}
}
}
return visit_order;
}

int main()
{
using T = unsigned;

//그래프 객체 생성
auto G = create_reference_graph<T>();
cout << "[입력 그래프]" << endl;
cout << G << endl;

//1번 정점부터 DFS 실행 & 방문 순서 출력
cout << "[DFS 방문 순서]" << endl;
auto dfs_visit_order = depth_first_search(G, 1);
for (auto v : dfs_visit_order)
cout << v << endl;
}

깊이 우선 탐색은 너비 우선 탐색과 다르게 스택과 재귀를 통해서 구현됩니다.
최단 경로나 미로 찾기 시 BFS가 더 유리하고 경로의 특징이 조건으로 주어질 경우 DFS를 사용합니다.

기존의 Edge와 Graph 객체들은 BFS와 동일합니다.
이전에 포스팅한 DFS Algorithm을 참고하시길 바랍니다.

while (!stack.empty())
{
auto current_vertax = stack.top();
stack.pop();

// 현재 정점을 이전에 방문하지 않았다면
if (visited.find(current_vertax) == visited.end())
{
visited.insert(current_vertax);
visit_order.push_back(current_vertax);

for (auto& e : G.edges(current_vertax))
{
//인접한 정점 중애서 방문하지 않은 정점이 있다면 스택에 추가
if (visited.find(e.dst) == visited.end())
{
stack.push(e.dst);
}
}
}
}

다른 부분은 위의 부분입니다.
스택은 LIFO 방식으로 작동하기 때문에 항상 가장 마지막 노드가 top()에 위치합니다.
다시 무한 루프를 돌면서 깊이 우선 탐색방식으로 스택을 채우고, 또 다시 비우면서 탐색합니다.

다음 시간에는 프림의 알고리즘을 분석하겠습니다.

요람에서 코드까지