그래프(Graph) DFS 탐색 구현하기

그래프와 BFS DFS의 개념, 그래프 구현방법은 이전 포스팅을 참고 

☞그래프(Graph)와 BFS, DFS

☞그래프(Graph) 인접 리스트(adjacency list)로 구현하기

---

그래프 생성하기

먼저 그래프를 생성하고 아래 그림과 같은 관계를 갖는 노드들을 만들겠습니다. (그래프와 구현은 이전 포스팅에 있습니다 ☞그래프(Graph) 인접 리스트(adjacency list)로 구현하기.)

public class DFSBFS {
    public static void main(String[] args) {
        Graph graph = new Graph(5);
        graph.setNode();
        graph.addEdge(0, 1);
        graph.addEdge(0, 4);
        graph.addEdge(1, 0);
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 1);
        graph.addEdge(2, 3);
        graph.addEdge(3, 1);
        graph.addEdge(3, 4);
        graph.addEdge(3, 2);
        graph.addEdge(4, 3);
        graph.addEdge(4, 0);
        graph.addEdge(4, 1);
    }
}

방문한 노드 표시하기

노드를 한번씩만 방문 하기 위해서 방문 한 노드를 표시 해주는 필드를 하나 선언 하겠습니다. 기본적으로 false로 선언하고, 방문한 노드에는 true로 표기합니다.

class Node {
    int data;
    LinkedList adjacent;
    boolean visited;

    public Node(int data) {
        this.data = data;
        adjacent = new LinkedList<>();
        visited = false;
    }
}

재귀적으로 모든 노드들을 탐색하기

시작 노드를 기준으로 모든 노드들을 탐색하기 위해서, 해당 노드의 인접한 노드들의 탐색을 재귀적으로 호출합니다. visit()이라는 메소드는 해당 노드를 방문했다고 표시해주고, 일련의 작업을 진행합니다. 여기서는 데이터를 출력하도록 했습니다. 탐색 순서는 위의 main메소드에서 입력한 순서를 기준으로 진행됩니다.

class Graph{

    . . .

    void dfs(Node node) {
        visit(node);
        //방문한 노드의 인접한 노드들도 재귀적으로 방문
        for (Node n : node.adjacent) {
            if(!n.visited) dfs(n);
        }
    }

    //시작 인덱스로 탐색 시작시에 필요한 메소드
    void dfs(int index) {
        dfs(nodes[index]);
    }

    void visit(Node node) {
        node.visited = true;
        System.out.print(node.data+"\t");
    }
}

실행결과

main메소드에서 인덱스 0부터 시작하는 경우 탐색을 아래와 같이 진행합니다.

public static void main(String[] args) {
    . . . 
    graph.dfs(0);
}

//실행결과
//0	1	4	3	2	

main메소드에서 인덱스 4부터 시작하는 경우 탐색을 아래와 같이 진행합니다.

public static void main(String[] args) {
    . . . 
    graph.dfs(4);
}

//실행결과
//4	 3	1	0	2