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

스택을 이용하여 그래프를 순회하는 방법

나를 먼저 방문하고 그 다음으로 인접한 노드를 차례대로 방문(단, 방문했던 노드는 방문하지 않는다.)

 

예제)

1 -> 2 -> 3 -> 4 -> 5 -> 6

 

연습)

다음 그래프에 대하여 1을 지가으로 DFS한 결과는? (단, 인접한 노드가 여러개일 경우 노드 번호가 작은 노드부터 방문한다.)

1 -> 2 -> 3 -> 5 -> 6 -> 7 -> 8 -> 9 -> 4 -> 10 -> 11 

 

-깊이 우선 탐색의 과정

DFS(Vertex, Visited); 

1. V를 방문했다고 처리한다.

2. V와 인접한 모든 W(인접노드)에 대하여 다음을 반복

3. 만약 W를 아직 방문하지 않았다면

4. DFS(W, Visited);

5. 방문순서 반환

 

-구현

void DFS(Graph graph, int v, boolean[] visited) {
 
    visited[v] = true;
 
    for ( int i = 0; i < graph[i].size(); i++ ) {
        int w = graph[v][i];
        
        if ( !visited[w] ) {
            DFS( graph, w, visited );
        }        
    }
}

 

- 실습

graph[1] = [2, 4]

graph[2] = [1, 3, 4]

graph[3] = [2, 5, 6, 7]

graph[4] = [1, 2]

graph[5] = [3]

graph[6] = [3, 7]

graph[7] = [3, 6]

 

-> DFS( graph, 1, visited); visited = [F, T, F, F, F, F, F, F];

-> DFS( graph, 2, visited); visited = [F, T, T, F, F, F, F, F];

-> DFS( graph, 3, visited); visited = [F, T, T, T, F, F, F, F];

-> DFS( graph, 5, visited); visited = [F, T, T, T, F, T, F, F];

-> DFS( graph, 6, visited); visited = [F, T, T, T, F, T, T, F];

-> DFS( graph, 7, visited); visited = [F, T, T, T, F, T, T, T];

-> DFS( graph, 4, visited); visited = [F, T, T, T, T, T, T, T];

 

- 구현

package org.example;
 
import java.util.LinkedList;
 
// 정점갯수, 간선갯수
// 9 12
// 1 2
// 1 3
// 2 3
// 2 4
// 2 6
// 3 7
// 4 5
// 4 7
// 4 8
// 5 6
// 7 8
// 8 9
 
public class DFS {
 
    private Graph graph;
    private boolean[] visited;
 
    public DFS() {
        Graph graph = new Graph(9);
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 3);
        graph.addEdge(2, 4);
        graph.addEdge(2, 6);
        graph.addEdge(3, 7);
        graph.addEdge(4, 5);
        graph.addEdge(4, 7);
        graph.addEdge(4, 8);
        graph.addEdge(5, 6);
        graph.addEdge(7, 8);
        graph.addEdge(8, 9);
 
        this.graph = graph;
        visited = new boolean[10];
    }
 
    public void dfs(Graph graph, int x, boolean[] visited) {
 
        System.out.print(x + " ");
        visited[x] = true;
 
        LinkedList<Integer>[] adjacencyList = graph.getAdjacencyList();
        for (int i = 0; i < adjacencyList[x].size(); i++) {
            int y = adjacencyList[x].get(i);
            if (!visited[y]) {
                dfs(graph, y, visited);
            }
        }
 
    }
 
    public static void main(String[] args) {
        DFS dfs = new DFS();
        dfs.graph.printGraph();
 
        dfs.dfs( dfs.graph, 1, dfs.visited );
 
    }
 
}
 
class Graph {
    private int vertex;
    private LinkedList<Integer>[] adjacencyList;
 
    public LinkedList<Integer>[] getAdjacencyList() {
        return adjacencyList;
    }
 
    public Graph(int vertex) {
        this.vertex = vertex;
        adjacencyList = new LinkedList[vertex + 1];
 
        // 각 인접 리스트를 초기화
        for (int i = 0; i < adjacencyList.length; i++) {
            adjacencyList[i] = new LinkedList<>();
        }
    }
 
    // 간선 추가
    public void addEdge(int v, int w) {
        adjacencyList[v].add(w);
        adjacencyList[w].add(v);
    }
 
    // 그래프 출력
    public void printGraph() {
        for (int i = 1; i < adjacencyList.length; i++) {
            System.out.print("Vertex " + i + " : ");
            for (Integer v : adjacencyList[i]) {
                System.out.print(v + " ");
            }
            System.out.println();
        }
    }
 
}
 
 

 

연습문제

-바이러스

https://www.acmicpc.net/problem/2606

- 단지번호붙이기

https://www.acmicpc.net/problem/2667