[자료구조 & 알고리즘] 8. 그래프 순회

그래프 순회

1. 그래프 순회 (Graph Traversal)

• 그래프의 각 정점을 방문하는 과정을 말함.

• 그래프 탐색(Graph Search)이라고도 함.

• 트리는 부모 -> 자식으로 각 노드끼리 방향이 단방향으로 정해져 있지만, 그래프는 각 정점끼리 양방향으로 이어질 수 있기 때문에(무향 그래프일 때, 또는 유향 그래프에서 각 정점이 서로를 향하는 엣지를 가질 때) A 정점에 B 정점을 방문한 후 B 정점에서 다시 A 정점으로 방문할 가능성이 존재.

     - 따라서, 한 번 방문한 곳은 방문한 곳이라는 표시를 해야 함.

 

2. 인접 리스트의 그래프 순회

• 너비 우선 탐색 (BFS, Breadth First Search)

     - 시작 정점의 가까운 곳 우선 탐색 -> 그 다음 떨어진 곳 탐색 -> 그 다음 떨어진 곳 탐색...

     - 시작점에서부터 가까운 순서대로 탐색한다는 특성을 이용하여 최단 경로 찾기 등에 많이 쓰임.

private static void bfs(List<List<Integer>> graph, int startVertex) {
    Set<Integer> visitedVertex = new HashSet<>();
    Queue<List<Integer>> vertexQueue = new LinkedList<>();
    vertexQueue.add(graph.get(startVertex));
    visitedVertex.add(startVertex);
    while(!vertexQueue.isEmpty()) {
        List<Integer> currentVertex = vertexQueue.poll();
        for(int vertex : currentVertex) {
            if(!visitedVertex.contains(vertex)) {
                vertexQueue.add(graph.get(vertex));
                visitedVertex.add(vertex);
            }
        }
    }
    System.out.println(visitedVertex);
}

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

     - 한 정점에 방문하면 그 정점에 연결된 모든 정점을 방문함. 다음 정점에서 또 그 정점에 연결된 모든 정점을 방문...

private static void dfs(List<List<Integer>> graph, int currentVertex, Set<Integer> visitedVertex) {
    visitedVertex.add(currentVertex);
    for(int vertex : graph.get(currentVertex)) {
        if(!visitedVertex.contains(vertex)) {
            dfs(graph, vertex, visitedVertex);
        }
    }
}

 

3. 인접 행렬의 그래프 순회

• 너비 우선 탐색

private static void bfs(int[][] adjMatrix, int startVertex) {
    Set<Integer> visitedVertex = new HashSet<>();
    Queue<int[]> vertexQueue = new LinkedList<>();
    vertexQueue.add(adjMatrix[startVertex]);
    visitedVertex.add(startVertex);
    while(!vertexQueue.isEmpty()) {
        int[] currentVertex = vertexQueue.poll();
        for(int i = 0; i < currentVertex.length; i++) {
            if(currentVertex[i] == 1 && !visitedVertex.contains(i)) {
                vertexQueue.add(adjMatrix[i]);
                visitedVertex.add(i);
            }
        }
    }
    System.out.println(visitedVertex);
}

• 깊이 우선 탐색

private static void dfs(int[][] adjMatrix, int currentVertex, Set<Integer> visitedVertex) {
    visitedVertex.add(currentVertex);
    for(int i = 0; i < adjMatrix[currentVertex].length; i++) {
        if(adjMatrix[currentVertex][i] == 1 && !visitedVertex.contains(i)) {
            dfs(adjMatrix, i, visitedVertex);
        }
    }
}

 

4. 암시적 그래프의 그래프 순회

• 암시적 그래프는 엣지가 명시적으로 주어지지 않음. 연결은 그림과 설명으로 주어짐.

     - 예를 들어, 격자 그림이 주어지고, 검은 색 칸은 벽이고 흰 색 칸은 길이다. 이동은 상하좌우로만 가능하다. 이런 식으로 주어짐.

     - 이 경우, 정점 사이를 연결하는 엣지는 명시적으로 주어지지 않고, 상하좌우에 있는 흰 색 정점끼리 연결된다는 것을 유추할 수 있음.

• 따라서, 이러한 주어진 연결 조건에 따라 함수 형태가 달라짐.

     - 상하좌우의 정점을 탐색하기 위해 dr, dc를 사용하여 각 칸을 (-1, 0), (0, -1), (1, 0), (0, 1) 만큼 이동하며 탐색

     - 흰 색 칸만 갈 수 있다면 "0"에만 갈 수 있도록 if문 조건 추가.

• 너비 우선 탐색

private static void bfs(String[][] implicitGraph, int[] startVertex) {
    int[] dr = {-1, 0, 1, 0};
    int[] dc = {0, -1, 0, 1};
    int m = implicitGraph.length;
    int n = implicitGraph[0].length;
    boolean[][] visitedVertex = new boolean[m][n];
    Queue<int[]> vertexQueue = new LinkedList<>();
    vertexQueue.add(startVertex);
    visitedVertex[startVertex[0]][startVertex[1]] = true;
    while(!vertexQueue.isEmpty()) {
        int[] currentVertex = vertexQueue.poll();
        int r = currentVertex[0];
        int c = currentVertex[1];
        System.out.println("(" + r + ", " + c + ")");
        for(int i = 0; i < dr.length; i++) {
            int nextRow = r + dr[i];
            int nextColumn = c + dc[i];
            if(nextRow >= 0 && nextRow < m && nextColumn >= 0 && nextColumn < n && !visitedVertex[nextRow][nextColumn] && Objects.equals(implicitGraph[nextRow][nextColumn], "0")) {
                vertexQueue.add(new int[] {nextRow, nextColumn});
                visitedVertex[nextRow][nextColumn] = true;
            }
        }
    }
}

• 깊이 우선 탐색

private static void dfs(String[][] implicitGraph, int[] currentVertex, boolean[][] visitedVertex, int[] dr, int[] dc) {
    int r = currentVertex[0];
    int c = currentVertex[1];
    System.out.println("(" + r + ", " + c + ")");
    visitedVertex[r][c] = true;
    for(int i = 0 ; i < dr.length; i++) {
        int nextRow  = r + dr[i];
        int nextColumn = c + dc[i];
        if(nextRow >= 0 && nextRow < implicitGraph.length && nextColumn >= 0 && nextColumn < implicitGraph[0].length && !visitedVertex[nextRow][nextColumn] && Objects.equals(implicitGraph[nextRow][nextColumn], "0")) {
            dfs(implicitGraph, new int[]{nextRow, nextColumn}, visitedVertex, dr, dc);
        }
    }
}

 

5. 그래프 순회의 시간 복잡도

• 그래프의 순회는 BFS, DFS 모두 O(V+E) 임. 여기서 V+E는 (정점 개수) + (엣지 개수)

• 그래프는 한 정점에서 모든 엣지에 대해 방문을 함.

     - 이미 전에 방문했던 정점이 있어도 우선 방문해서 방문 여부를 확인한 후 돌아오기 때문