Depth First Search

구현 방법

  1. 탐색 시작 노드를 스택에 삽입하고 방문처리
  2. 스택의 최상단 노드의 인접한 노드 중 방문하지 않은 노드가 있다면 그 노드를 스택에 넣고 방문처리 방문하지 않은 노드가 없다면 스택의 최상단 노드를 꺼냄
  3. 2번의 과정을 수행할 수 없을 때까지 반복 (스택에 아무것도 없어질 때까지 반복)
#include <iostream>
#include <vector>
using namespace std;

// index 0은 사용하지 않음으로 배열을 하나 더 추가
bool visited[9]; 
vector<int> graph[9];

void dfs(int x)
{
	visited[x] = true;
	cout << x << " ";
	for (int i = 0; i < graph[x].size(); i++) // 인접한 노드 사이즈만큼 탐색
	{
		int y = graph[x][i];
		if (!visited[y]) // 방문하지 않았으면 즉 visited가 False일 때 not을 해주면 True가 되므로 아래 dfs 실행
            dfs(y); // 재귀적으로 방문
	}
}

int main(void)
{
    /* 위 그래프와 동일하게 정의 */
    graph[1].push_back(2);
    graph[1].push_back(3);
    graph[1].push_back(8);

    graph[2].push_back(1);
    graph[2].push_back(7);

    graph[3].push_back(1);
    graph[3].push_back(4);
    graph[3].push_back(5);

    graph[4].push_back(3);
    graph[4].push_back(5);

    graph[5].push_back(3);
    graph[5].push_back(4);

    graph[6].push_back(7);

    graph[7].push_back(2);
    graph[7].push_back(6);
    graph[7].push_back(8);

    graph[8].push_back(1);
    graph[8].push_back(7);

    dfs(1);
}
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

unordered_map<char, vector<char>> adjList;//인접리스트(노드, 연결되어있는 노드 배열)
vector<char> result;
unordered_set<char> visited;

void dfs(char node){
	visited.insert(node);//방문한 노드 체크
	result.push_back(node);
	
	for(char neighbor: adjList[node]){
		if(visited.find(neighbor) == visited.end()){//만약 방문한 적이 없다면 dfs
			dfs(neighbor);
		}
	}
}

주요 사항

장단점

장점

단점

Breath First Search

구현 방법

  1. 탐색 시작 노드를 큐에 삽입하고 방문 처리