[자료구조] 그래프, dfs, bfs

 

 

그래프란?

 

정점(vertice)과 정점간의 관계를 표현한 조직도

직접적인 관계가 있다면 두 정점 사이에 간선(edge)이 있고 간접적인 관계가 있다면 몇 개의 점과 선에 걸쳐서 이어진다.'

 

용어

 

정점(Vertice): 데이터가 저장되는 그래프의 기본 원소, 노드라고도 한다.

간선(Edge): 정점 간의 관계를 나타내는 선

사이클(Cycle): 한 정점에서 출발해 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 할 수 있음.

자기 루프(Self loop): 한 정점에서 출발한 간선이 다른 정점을 거치지않고 다시 자기 자신에게 돌아오면 자기루프를 가진다고 표현함.

차수(Degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수

 

그래프 구현

 

그래프를 구현하는 방식에는 인접행렬과 인접리스트 방식이 있다.

 

인접 행렬 (Adjacency matrix)

 

인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 2차원 배열 형태의 행렬이다.

이어져있다면 1, 그렇지 않다면 0으로 표시한다. 인접 행렬은 정점 간 관계 유무를 파악하는데 주로 사용한다.

가장 빠른 경로를 찾고자 할 때도 많이 사용된다. 다만 데이터가 커짐에 따라 2차원배열도 계속 커지기 때문에 많은 공간을 낭비하고, 모든 정점에 대한 간선 정보를 대입해야해서 O(n^2)의 시간 복잡도가 소요된다.

 

 

인접 리스트 (Adjacency list)

 

인접 리스트는 각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현한다. 인접 리스트는 인접 행렬에 비해 공간 낭비가 적어서 메모리를 효율적으로 사용할 수 있다. 또한 연결 정보를 탐색할 때도 O(n)의 시간이면 충반하다. 다만 특정 점들이 연결되어 있는지 확인하려면 시간이 오래 걸리고, 구현이 비교적 어렵다는 단점이 있다.

 

 

그래프 종류

 

 

 

무방향 그래프: 두 정점을 연결하는 간선에 방향이 없는 그래프

방향 그래프: 두 정점을 연결하는 간선에 방향이 있는 그래프

가중치 그래프: 두 정점을 이동할 때 가중치만큼의 비용이 드는 그래프

완전 그래프: 모든 정점이 간선으로 연결되어 있는 그래프

 

 

그래프 탐색

 

그래프의 정보를 저장했으면 해당 정보를 이용해서 뭔가 해야할 것이다.

그럴때 대표적으로 BFS, DFS 이 2가지 그래프 탐색 방법이 쓰인다.

 

DFS (Depth-First Search)

DFS(깊이 우선 탐색)은 하나의 정점에서 시작해 해당 경로를 끝까지 탐색한 후, 다음 경로로 넘어가 탐색한다. 하나의 경로를 끝까지 보기 때문에 운이 좋다면 원하는 자료를 몇 번 만에 찾을 수 있다.

재귀호출 혹은 스택을 사용해 구현한다.

 

BFS (Breadth-First Search)

BFS(너비 우선 탐색)은 시작 정점을 방문한 후, 인접한 모든 정점을 방문하는 방식이다. 주로 두 정점 사이의 최단 경로를 찾을 때 사용한다. 일반적으로 큐를 사용해서 현재 노드에서 갈 수 있는 노드를 모두 큐에 넣는 방식으로 구현한다.

 

예제

 

package graph;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Queue;

public class GraphSpace {

    public static void main(String[] args) {
        int[][] graph = {
                {0, 1, 1, 0, 0, 0, 0, 0, 0, 0}, // 0번 노드
                {1, 0, 1, 1, 0, 0, 0, 0, 0, 0}, // 1번 노드
                {1, 1, 0, 0, 1, 0, 0, 0, 0, 0}, // 2번 노드
                {0, 1, 0, 0, 1, 1, 0, 0, 0, 0}, // 3번 노드
                {0, 0, 1, 1, 0, 1, 1, 0, 0, 0}, // 4번 노드
                {0, 0, 0, 1, 1, 0, 0, 1, 1, 0}, // 5번 노드
                {0, 0, 0, 0, 1, 0, 0, 0, 1, 1}, // 6번 노드
                {0, 0, 0, 0, 0, 1, 0, 0, 1, 1}, // 7번 노드
                {0, 0, 0, 0, 0, 1, 1, 1, 0, 1}, // 8번 노드
                {0, 0, 0, 0, 0, 0, 1, 1, 1, 0}  // 9번 노드
        };

        boolean[] isVisit = new boolean[graph.length];
        System.out.print("bfs : ");
        bfs(graph,3);
        System.out.println();
        System.out.print("dfs : ");
        dfs(graph,3);
        System.out.println();
        System.out.print("dfs by recursion : ");
        dfsByRecur(graph,isVisit,3);

    }

    public static void bfs(int[][] graph, int start) {
        Deque<Integer> queue = new ArrayDeque<>();
        boolean[] visited = new boolean[graph.length]; // 방문 여부 배열

        queue.add(start);
        visited[start] = true; // 시작 노드 방문 처리

        while (!queue.isEmpty()) {
            int cur = queue.poll(); // 큐에서 현재 노드 꺼내기
            System.out.print(cur + " "); // 현재 노드 출력

            // 현재 노드와 연결된 모든 노드 탐색
            for (int i = 0; i < graph[cur].length; i++) {
                if (graph[cur][i] == 1 && !visited[i]) { // 연결되어 있고 방문하지 않은 노드
                    queue.add(i); // 큐에 추가
                    visited[i] = true; // 방문 처리
                }
            }
        }
    }
    // 스택을 사용한 dfs
    public static void dfs(int[][] graph, int start) {
        Deque<Integer> stack = new ArrayDeque<>(); // 스택 생성
        boolean[] visited = new boolean[graph.length]; // 방문 여부 확인 배열

        stack.push(start); // 시작 노드를 스택에 추가

        while (!stack.isEmpty()) {
            int cur = stack.pop(); // 현재 노드

            // 이미 방문한 노드라면 무시
            if (visited[cur]) {
                continue;
            }

            // 현재 노드 방문 처리
            visited[cur] = true;
            System.out.print(cur+" "); // 방문한 노드 출력

            // 현재 노드의 이웃 노드들을 스택에 추가 (역순으로 추가해 스택 순서 유지)
            for (int i = graph.length - 1; i >= 0; i--) {
                if (!visited[i] && graph[cur][i] == 1) {
                    stack.push(i);
                }
            }
        }
    }
    // dfs 재귀버전
    public static void dfsByRecur(int[][] graph, boolean[] isVisit, int start) {
        // 현재 노드 방문 처리
        isVisit[start] = true;
        System.out.print(start+" "); // 방문한 노드 출력

        // 인접 노드 탐색
        for (int i = 0; i < graph.length; i++) {
            if (graph[start][i] == 1 && !isVisit[i]) {
                dfsByRecur(graph, isVisit, i); // 재귀 호출
            }
        }
    }
}

 

 

실행화면