그래프의 순회(bfs, dfs)

이전 시간에 배운 트리의 순회 방법인 levelorder traversal(bfs), dfs와 그렇게 큰 차이는 없다. 다만, base condition에서 약간의 차이를 보인다.

💻bfs 코드

public static Set<String> bfs() {
		// graph 구조는 이전 것을 그대로 가져왔기 때문에 createGraph()의 바디는 생략하였음.
        HashMap<String, List<String>> graph = createGraph();

        // 첫번째 정점을 시작점으로 설정
        String startNode = "A";

        // 사전 세팅: 시작 정점을 넣는다
        LinkedHashSet<String> visited = new LinkedHashSet<>();
        Queue<String> q = new LinkedList<>();
        visited.add(startNode);
        q.offer(startNode);

        while (!q.isEmpty()) {
            String curNode = q.poll();

            for (String v : graph.get(curNode)) {
                if (!visited.contains(v)) {
                    visited.add(v);
                    q.offer(v);
                }
            }
        }

        return visited;
    }

• 🚩파이썬에서는 visited를 간단하게 리스트로 표현해서 if v not in visited:로 조건을 검사했지만, 자바에서는 ArrayList 타입의 visited로 v가 있는지 검사하면 순회하면서 모든 요소를 탐색해야 하기 때문에 O(N)이 걸린다.
  • 🔨따라서 순서가 보장되는 LinkedHashSet으로 visited 객체를 만들면 HashSet의 contains()가 HashMap의 containsKey(Object key) 기반으로 만들어졌기 때문에 O(1)만 걸리게 할 수 있다.

잘 기억이 안나면 해시맵의 메서드 종류를 참고 할 것!

⏰따라서, 총 시간복잡도는 모든 정점과 간선을 visited와 queue를 통해서 한 번만 처리할 수 있기 때문에 $O(V+E)$만 걸린다.

💻dfs 코드

public static Set<String> dfs(String curNode) {
        HashMap<String, List<String>> graph = createGraph();
        visited.add(curNode); // 노드 방문 후 저장
		// 노드 순회
        for (String v : graph.get(curNode)) {
            if (!visited.contains(v)) {
                dfs(v);
            }
        }
        return visited;
    }

• 트리의 preorder 방식과 유사하다. 즉, 노드를 방문할 때 visited에 저장하고, 그 다음에 재귀적으로 curNode에 연결된 정점들을 순회한다.
• 💡dfs를 호출하면 visited도 초기화되기 때문에, visited를 전역 변수로 만들었다.

⏰마찬가지로 모든 정점과 for문으로 간선으로 연결된 정점들을 탐색하기 때문에 $O(V+E)$ 시간복잡도가 걸린다.