깊이우선 탐색/넓이우선 탐색 (DFS/BFS)

■ 설명

그래프를 탐색하는 방법에는 두가지가있다. 첫번째는 깊이우선 탐색(DFS) 이고 두번째는 넓이 우선 탐색(BFS)이다. DFS 의  인접한 노드를 타고 들어가며 탐색하는 방식이고 BFS 는 탐색 시작 노드부터 같은 레벨(?) 에 있는 노드부터 탐색하는 방식이다.

■ 구현 ( 코드 )

[Main.cpp 일부]

Colored By Color Scripter™

#include <iostream> #include <memory.h> #include <vector> // DFS stack 용  #include <list>      // BFS queue 용  #include "Graph.h" using namespace std; void Traverse_DFS(const Graph& graph, const KEY& startNode) {     vector<KEY> nodeStack;         bool* checkedNodes = new bool[graph.GetSize()];          memset(checkedNodes, 0, sizeof(bool)*graph.GetSize());     nodeStack.push_back(startNode);     checkedNodes[startNode] = true;     list<KEY> adjacentNodes;     while (nodeStack.size())     {         KEY popedNode = nodeStack.back();         nodeStack.pop_back();         // 확인용 데이터 출력         cout << "Current Node : " << popedNode << endl;         graph.FindAdjacentNodes(popedNode, &adjacentNodes);         for (auto& node : adjacentNodes)         {             if (checkedNodes[node])                 continue;             nodeStack.push_back(node);             checkedNodes[node] = true;         }         adjacentNodes.clear();     } } void Traverse_BFS(const Graph& graph, const KEY& startNode) {     list<KEY> nodeQueue;     bool* checkedNodes = new bool[graph.GetSize()];     memset(checkedNodes, 0, sizeof(bool)*graph.GetSize());     nodeQueue.push_back(startNode);     checkedNodes[startNode] = true;     list<KEY> adjacentNodes;     while (nodeQueue.size())     {         KEY popedNode = nodeQueue.front();         nodeQueue.pop_front();         // 확인용 데이터 출력         cout << "Current Node : " << popedNode << endl;         graph.FindAdjacentNodes(popedNode, &adjacentNodes);         for (auto& node : adjacentNodes)         {             if (checkedNodes[node])                 continue;             nodeQueue.push_back(node);             checkedNodes[node] = true;         }         adjacentNodes.clear();     } }

DFS 는 스택으로, BFS는 큐로 구현했다. 생각나는대로 구현 했다만 아마 가장 일반적인 방법일것이다. 스택과 큐라는 점 외에는 로직상 DFS, BFS의 차이가 없다.

■ 실행 결과

[Main.cpp 일부]

Colored By Color Scripter™

int main() {     Graph* graph = Graph::Create(7);     graph->AddNode(0);     graph->AddNode(1);     graph->AddNode(2);     graph->AddNode(3);     graph->AddNode(4);     graph->AddNode(5);     graph->AddNode(6);     graph->AddEdge(0, 1);     graph->AddEdge(1, 3);     graph->AddEdge(1, 4);     graph->AddEdge(0, 2);     graph->AddEdge(2, 5);     graph->AddEdge(2, 6);     cout << "::Traversal_DFS::" << endl;     Traverse_DFS(*graph, 0);     cout << endl;     cout << "::Traversal_BFS::" << endl;     Traverse_BFS(*graph, 0);     cout << endl;     graph->Release();     delete graph;     graph = nullptr;     return 0; }

■소스 코드

Downloading Traversal_vs2015_project