[코지] DFS, BFS 정리

DFS (Depth-First-Search)

1. 사용 시기

    그래프 를 순회 할때 사용합니다. 

2. 구현 방법 

    stack 을 사용하여 구현 합니다.

stack first-in last-out

3. 동작 순서

    1. 시작 할 node를  stack에 집어 넣습니다.

    2. stack에 넣은 것 1개를 빼서 출력 

    3. 뺀것과 열결된 node를 모두 stack에 입력 

    4. 2, 3번 을 무한 반복

    5. stack에 더이상 없으면 프로그램을 종료

 

DFSR (Depth-First-Search-Recursion)

1. 사용 시기

    그래프 를 순회 할때 사용합니다. 

2. 구현 방법 

 재귀 함수를 사용하여 구현 합니다.

3. 동작 순서

    1. 시작 할 node를  재귀함수에 넣습니다.

    2. 재귀 함수에서 바로 입력 받는 node를 출력합니다.

    3. 입려받은 node의 자식 노드를 재귀함수에 넣습니다.

    4. 1, 3번 을 무한 반복

    5. 재귀가 끝나면 프로그램을 종료

 

BFS (Breadth-First-Search)

1. 사용 시기

    그래프 를 순회 할때 사용합니다

2. 구현 방법

    queue를 사용하여 구현 합니다.

queue는 first-in first-out

3. 동작 순서 

    1. 시작 할 node를  queue에 집어 넣습니다.

    2. queue에 넣은 것 1개를 빼서 출력

    3. 뺀것과 열결된 node를 모두 queue에 입력 

    4. 2, 3번 을 무한 반복

    5. queue에 더이상 없으면 프로그램을 종료

 

C++ 전체 코드 구현 

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <stack>


class Node {
public:
	int data;
	bool marked;
	std::list<Node*> adjacent;
	
	Node(int data) {
		this->data = data;
		this->marked = false;
	}
	
	bool operator==(const Node &rhs) const {
		return this->data == rhs.data;
	}
};

class Graph {
public:
	std::vector<Node*> nodes;
	Graph(int size) {
		for(auto i = 0; i < size; i++) {
			nodes.push_back(new Node(i));
		}
	}
	
	void addEdge(int i, int j){
		if (std::find(nodes[i]->adjacent.begin(), nodes[i]->adjacent.end(), nodes[j]) == nodes[i]->adjacent.end()) {
			//std::cout << nodes[i]->data << " : " << nodes[j]->data << std::endl;
			nodes[i]->adjacent.push_back(nodes[j]);
		}
		
		if (std::find(nodes[j]->adjacent.begin(), nodes[j]->adjacent.end(), nodes[i]) == nodes[j]->adjacent.end()) {
			//std::cout << nodes[j]->data << " : " << nodes[i]->data << std::endl;
			nodes[j]->adjacent.push_back(nodes[i]);
		}
	}
	
	void dfs(int start) {
		//stack
		std::stack<Node*> s;
		s.push(nodes[start]);
		nodes[start]->marked = true;
		Node *top;
		while (!s.empty()) {
			top = s.top();
			s.pop();
			std::cout << top->data << " ";
			for (auto item : top->adjacent){
				if (item->marked == false) {
					item->marked = true;
					s.push(item);	
				}
			}
		}
		std::cout<< "\n";
		
	}
	
	void dfsr(int start) {
		nodes[start]->marked = true;
		std::cout << nodes[start]->data << " ";
		for(auto item : nodes[start]->adjacent) {
			if (item->marked == false) {
				dfsr(item->data);	
			}
		}
	}
	
	void bfs(int start) {
		//queue
		//stack
		std::deque<Node*> d;
		d.push_front(nodes[start]);
		nodes[start]->marked = true;
		Node *top;
		while (!d.empty()) {
			top = d.back();
			d.pop_back();
			std::cout << top->data << " ";
			for (auto item : top->adjacent){
				if (item->marked == false) {
					item->marked = true;
					d.push_front(item);	
				}
			}
		}
		std::cout<< "\n";
		
	}
};

int main(int argc, char* argv[]) {
	printf("Hello, goorm!\n");
	
	Graph graph(9);
	graph.addEdge(0, 1);
	graph.addEdge(1, 2);
	graph.addEdge(1, 3);
	graph.addEdge(2, 4);
	graph.addEdge(2, 3);
	graph.addEdge(3, 4);
	graph.addEdge(3, 5);
	graph.addEdge(5, 6);
	graph.addEdge(5, 7);
	graph.addEdge(6, 8);

	//graph.dfs(0);
	//graph.bfs(3);
	graph.dfsr(0);
	return 0;
}

 

 

 

참조 강의

https://www.youtube.com/watch?v=_hxFgg7TLZQ&t=9&ab_channel=%EC%97%94%EC%A7%80%EB%8B%88%EC%96%B4%EB%8C%80%ED%95%9C%EB%AF%BC%EA%B5%AD