[DATASTRUCTURE] DFS, BFS

DFS : 깊이 우선 탐색

참고 : http://blog.eairship.kr/268

BFS : 너비 우선 탐색

참고 : http://blog.eairship.kr/269

DFS CODE - stl없이 구현

#pragma once #include <iostream> using namespace std; #define NODE_COUNT 10 #define ABLE 1 #define INABLE -1 #define VISITED 1 #define DIDNT_VISIT -1 typedef struct Graph { int num; int Child[NODE_COUNT]; }; Graph*DFS_Graph = new Graph[NODE_COUNT]; int Visit[NODE_COUNT]; void Initialize() { for (int i = 0; i < NODE_COUNT; i++) { Visit[i] = DIDNT_VISIT; for (int j = 0; j < NODE_COUNT; j++) { DFS_Graph[i].Child[j] = INABLE; } } } void Graph_Initialize() { DFS_Graph[1].Child[2] = ABLE; DFS_Graph[1].Child[3] = ABLE; DFS_Graph[2].Child[1] = ABLE; DFS_Graph[2].Child[4] = ABLE; DFS_Graph[2].Child[5] = ABLE; DFS_Graph[3].Child[1] = ABLE; DFS_Graph[3].Child[6] = ABLE; DFS_Graph[3].Child[7] = ABLE; DFS_Graph[4].Child[2] = ABLE; DFS_Graph[4].Child[8] = ABLE; DFS_Graph[5].Child[2] = ABLE; DFS_Graph[5].Child[8] = ABLE; DFS_Graph[6].Child[3] = ABLE; DFS_Graph[6].Child[8] = ABLE; DFS_Graph[7].Child[3] = ABLE; DFS_Graph[7].Child[8] = ABLE; DFS_Graph[8].Child[4] = ABLE; DFS_Graph[8].Child[5] = ABLE; DFS_Graph[8].Child[6] = ABLE; DFS_Graph[8].Child[7] = ABLE; } void DFS(int node_num) { cout << node_num << endl; Visit[node_num] = VISITED; /*for (int i = 0; i < NODE_COUNT; i++) { cout << i<<" : "<<Visit[i] << " "; } system("pause");*/ for (int i = 0; i < NODE_COUNT; i++) { if (DFS_Graph[node_num].Child[i] != INABLE && Visit[i] == DIDNT_VISIT) { DFS(i); } } }

DFS CODE (stack) - 작은 수로 간다는 조건은 없음

#include <iostream> #include <vector> #include <stack> #include <fstream> using namespace std; vector<int> visit; vector<vector<int>>graph; stack<int> DFS_stack; void DFS() { DFS_stack.push(1); visit[1] = 1; while (!DFS_stack.empty()) { int index = DFS_stack.top(); DFS_stack.pop(); cout << index << " "; for (int j = 0; j < graph[index].size(); j++) { if (visit[graph[index][j]] == 0) { visit[graph[index][j]] = 1; DFS_stack.push(graph[index][j]); } } } } int main() { ifstream fcin; fcin.open("graph_input.txt"); int node_count, edge_count, start_index, end_index; fcin >> node_count >> edge_count; graph = vector<vector<int>>(node_count + 1); visit = vector<int>(node_count + 1, 0); while (edge_count--) { fcin >> start_index >> end_index; graph[start_index].push_back(end_index); graph[end_index].push_back(start_index); } DFS(); system("pause"); }

BFS CODE

#include <iostream> #include <iostream> #include <vector> #include <queue> #include <fstream> using namespace std; vector<int> visit; vector<vector<int>>graph; queue<int> BFS_queue; void BFS() { BFS_queue.push(1); visit[1] = 1; while (!BFS_queue.empty()) { int index = BFS_queue.front(); BFS_queue.pop(); cout << index << " "; for (int j = 0; j < graph[index].size(); j++) { if (visit[graph[index][j]] == 0) { visit[graph[index][j]] = 1; BFS_queue.push(graph[index][j]); } } } } int main() { ifstream fcin; fcin.open("graph_input.txt"); int node_count, edge_count,start_index,end_index; fcin >> node_count >> edge_count; graph = vector<vector<int>>(node_count + 1); visit = vector<int>(node_count + 1,0); while (edge_count--) { fcin >> start_index >> end_index; graph[start_index].push_back(end_index); graph[end_index].push_back(start_index); } BFS(); system("pause"); }