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);
		}
	}
}

주요 사항

• 그래프 구현 방식 벡터가 요소인 배열로 구현하였음. graph[1]에는 1번과 연결된 요소들로 구성된 벡터가 들어 있음
• 방문 여부를 체크하기 위해 visited array가 존재

장단점

장점

• 현 경로상의 노드만을 기억하므로 비교적 적은 저장공간을 필요로 한다.
• 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

단점

• 해가 없는 경로에 깊게 빠질 수 있다.
• 정답이 다수인 경우, 해당 정답이 최적이 아닐 수 있다.(DFS는 정답을 찾으면 탐색 종료)

Breath First Search

구현 방법

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