[Algorithm] Graph Traversal BFS, DFS

Graph Traversal

그래프를 순회 해본다.

 

 

 

순회방식

• BFS: 너비 우선 탐색
• DFS: 깊이 우선 탐색

 

 

BFS 구현

BFS 는 queue 를 이용 하면된다.

• 1. 처음 방문할 노드를 택한다.
• 2. 방문한 노드를 큐에 넣는다.
• 3. 큐에서 꺼내고 방문 했다고 체크 한다.
• 4. 방문한 노드에 인접한 노드를 큐에 넣어준다.
• 5. 2~4 까지 queue 가 비워질때 까지 반복한다.

 

 

코드

    public void graphTraversalBFS(ArrayList<ArrayList<Integer>> graph, int startNode) {
        ArrayList<Integer> checkVisit = new ArrayList<Integer>();
        Queue<Integer> queue = new LinkedList<>();
        queue.add(startNode);
        while(!queue.isEmpty()) {
            int node = queue.poll();

            if(!checkVisit.contains(node)) {
                checkVisit.add(node);
                System.out.println(node);
            }

            for(int i = 0; i < graph.get(node).size(); i++) {
                if(!checkVisit.contains(graph.get(node).get(i))) {
                    queue.add(graph.get(node).get(i));
                }
            }

        }
    }

 

 

 

 

 

DFS 구현

 

코드

    public void DFS(ArrayList<ArrayList<Integer>> graph, int node) {
        mVisited.add(node);
        System.out.println(node);
        for(int i = 0; i < graph.get(node).size(); i++) {
            if(!mVisited.contains(graph.get(node).get(i))) {
                DFS(graph, graph.get(node).get(i));
            }
        }
    }

    public void graphTraversalDFS(ArrayList<ArrayList<Integer>> graph, int node) {
        // 시작점을 주고 탐색 시작
        DFS(graph, node);
        
        // 해당 부분은 그래프가 쪼개져 있을 경우 전부 탐색 하기 위한 반복
        for( int i = 1; i < graph.size(); i++ ) {
            if(!mVisited.contains(i)) {
                DFS(graph, i);
            }
        }
    }

 

 

 

 

전체코드

 

구현코드:

https://github.com/rnrl1215/algorithm-base/blob/master/src/main/java/algorithm/graph/ListGraphExample.java

 

테스트 코드:

https://github.com/rnrl1215/algorithm-base/blob/master/src/test/java/GraphTest.java