DFS 나름 이론정리

개념

• 깊이 우선으로 탐색하는 알고리즘

• 그래프가 위와 같이 주어지면
  1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12
  순서로 탐색함.

활용함수

• 재귀함수

코드구현방법

1. 그래프 초기 배열 생성
2. 방문 배열 생성
3. 노드 방문 처리하고 그래프의 해당 노드를 돌면서 방문하지 않았으면 재귀적으로 방문처리.

코드

let graph = [[], [2,7,8],[1,3,6],[2,4,5],[3],[3],[2],[1],[1,9,12],[8,10,11],[9],[9],[8]];
//순서를 맞춰주기 위해 index 0 은 빈배열을 넣어준다.
let visited = new Array(graph.length+1).fill(false);

dfs(graph,1,visited);

function dfs(graph, v, visited){
	visited[v] = true;
    for(let i=0; i<graph[v].length; i++){
    	if(visited[i] == false) dfs(graph, i, vistied);
    }
}