DFS(깊이우선탐색,Depth-First-Search)

깊이 우선탐색은 더 깊이 들어갈 수 있을 때 까지 들어간다고 생각하자.

1) 시작정점을 '방문함' 으로 바꾼다.(따로 방문확인 배열이 존재함)

2) 그리고 방문한 정점과 이웃하고 있는 정점중에 아직 방문하지 않은 곳을 선택하여 이를 선택하여 시작정점으로 다시 1)을 수행

3) 더 이상 시작정점이 방문하지 않은 인접 정점이 없으면 이전 정점으로 돌아가서 2)를 수행

4) 이전 정점으로 돌아가도 더이상 방문할 곳이 없다면 그래프의 모든 정점을 방문한 것이다.

5) 탐색을 종료

인접행렬

public boolean[] visited;
public int[][] graph;

public void dfs(int node) { // node == node index
    visited[node] = true;

    for (int i = 0; i < graph[node].length; i++) {
        if (graph[node][i] == 1 && visited[i] == false) {
            dfs(i);
        }
    }
}

// 그래프가 disconnected 이거나 방향그래프여서 모든 노드가 방문 불가능할때, 모든 노드 방문 시키기
public void dfsAll() {
    for (int i = 0; i < graph.length; i++) {
        if (visited[i] == false) {
            dfs(i);
        }
    }
}

인접리스트

public boolean[] visited;
public ArrayList<ArrayList<Integer>> graph;

public void dfs(int node) { // node == node index
    visited[node] = true;

    ArrayList<Integer> connectNodeList = graph.get(node);
    for (int i = 0; i < connectNodeList.size(); i++) {
        int connectNode = connectNodeList.get(i);
        if (visited[connectNode] == false) {
            dfs(connectNode);
        }
    }
}

public void dfsSimple(int node) { // node == node index
    visited[node] = true;

    for (int connectNode: graph.get(node)) { // graph.get(node) => ArrayList가 나오고 이걸 for로 돔.
        if (visited[connectNode] == false) {
            dfs(connectNode);
        }
    }
}

// 그래프가 disconnected 이거나 방향그래프여서 모든 노드가 방문 불가능할때, 모든 노드 방문 시키기
public void dfsAll() {
    for (int i = 0; i < graph.length; i++) {
        if (visited[i] == false) {
            dfs(i);
        }
    }
}