[Algorithm] DFS (깊이 우선 탐색)

 

 

출처: https://sustainable-dev.tistory.com/44

 

 

 

 

 

 

** C++

 

#include <iostream>
#include <vector>

using namespace std;

int number = 7;
int visited[7];
vector<int> index[8];

void dfs(int x) { // stack 사용하지 않고 재귀함수 이용 
	if (visited[x]) return;
	visited[x] = true;
	cout << x << ' ';
	for (int i = 0; i < index[x].size(); i++) {
		int y = index[x][i];
		dfs(y);
	}
}

int main(void) {
	index[1].push_back(2);
	index[2].push_back(1);
	
	index[1].push_back(3);
	index[3].push_back(1);
	
	index[2].push_back(3);
	index[3].push_back(2);
	
	index[2].push_back(4);
	index[4].push_back(2);
	
	index[2].push_back(5);
	index[5].push_back(2);

	index[4].push_back(5);
	index[5].push_back(4);
	
	index[3].push_back(6);
	index[6].push_back(3);
	
	index[3].push_back(7);
	index[7].push_back(3);
	
	index[6].push_back(7);
	index[7].push_back(6);
	
	dfs(1); // 시작점 1 
	return 0; 
}

 

 

 

 

** Javascript

 

let visited = [];
let stack = new Array(8).fill([]);

function dfs(top) {
    if (visited[top]) { // 모든 정점 방문 시
        return;
    }
    visited[top] = true; // 방문 표시
    console.log(top);
    
    for (let i = 0; i < stack[top].length; i++) {
        let y = stack[top][i];
        dfs(y);
    }
}

stack[1].push(2);
stack[2].push(1);

stack[1].push(3);
stack[3].push(1);

stack[2].push(3);
stack[3].push(2);

stack[2].push(4);
stack[4].push(2);

stack[2].push(5);
stack[5].push(2);

stack[3].push(6);
stack[6].push(3);

stack[3].push(7);
stack[7].push(3);

stack[4].push(5);
stack[5].push(4);

stack[6].push(7);
stack[7].push(6);

dfs(1);