그래프 탐색 (계속 추가)

<DFS>

초기 작업 : 인접 리스트로 그래프 표현, 방문 배열 초기화, 시작 노드를 스택에 삽입

pop을 수행하여 노드를 꺼냄 → 꺼낸 노드를 탐색 순서에 기입

→ 인접 노드를 스택에 삽입, 방문 배열 체크

→ 스택에 값이 없을 때까지 반복, 다녀간 노드는 재삽입하지 않음

 

<BFS>

초기 작업 : 인접 리스트로 그래프 표현, 방문 배열 초기화, 시작 노드를 큐에 삽입

큐에서 노드를 꺼냄 →  꺼낸 노드를 탐색 순서에 기입

→ 인접 노드를 큐에 삽입, 방문 배열 체크

→ 큐에 값이 없을 때까지 반복, 다녀간 노드는 재삽입하지 않음

 

<가중치 없는 인접 리스트>

vector<vector<int>> A

vector<vector<int>> list = {{2,3}, {4,5}, {4}, {5}, {}};

 

 

<가중치 있는 인접 리스트>

vector<vector<pair<int,int>>> A

vector<vector<pair<int, int>>> list = {{{2,8}, {3,3}}, {{4,4}, {5,15}}, {{4,13}}, {{5,2}}, {}};