그래프 이론 - BFS/DFS 구현해보기

그래프란?

그래프는 정점(Vertex)들과 간선(Edge)들의 집합으로 구성된 자료구조이다.

그래프의 종류

정점의 위치나, 간선의 순서들은 그래프를 정의하는 데 사용되지 않는다.

트리도 그래프의 일종이나, 그래프는 트리와 다르게 정점마다 간선을 가지지 않을 수 있다.

그래프는 트리와 다르게 계층 구조의 형태가 아니므로, 역시 노드 간에 부모-자식 계층 관계가 성립하지 않는다. 따라서 루트 노드의 개념도 없다.

---

그래프의 종류

그래프는 정점이나 간선에 추가적인 속성을 부여하거나, 정점이 존재할 수 있는 방법을 다양하게 함으로써 여러 방식의 그래프로 표현이 가능하다.

방향 그래프( Directed Graph )

• 대표적인 그래프의 종류
• 정점을 잇는 간선들이 방향을 가진다.
• 위 그림의 첫번째 그래프에서 정점 2와 정점 3을 사이의 간선은 서로 다른 간선이다. 방향이 서로 다르다.

가중치 그래프( Weighted Graph )

• 각 간선에 가중치(weight)가 부여된 그래프
• 두 도시 사이의 거리와 같이 두 정점 사이의 관계를 나타내는 데 유용하다.

DAG ( Directed Acyclic Graph )

• 사이클이 없는 방향 그래프
• 한 정점에서 출발하여 다시 본인으로 돌아오는 경로가 존재하지 않는 그래프를 의미한다
• 여러 작업들의 의존 관계를 표현할 때 주로 사용한다

---

그래프의 경로

• 경로란, 시작 정점에서 끝 정점까지 연결된 간선들을 순서대로 나열한 것을 말한다.
• 경로 중에서, 반복되는 정점이 없이 한 번씩만 거치는 경로를 단순 경로(Simple Path)라 한다.

---

그래프의 표현

• 각 정점이 간선에 대한 정보를 포함하도록 구현해야 하는데, 이 간선 정보를 어떻게 표현하느냐에 따라 크게 2가지로 구분할 수 있다.

인접 행렬( Adjency Matrix )

• 인접 행렬은 그래프의 선형 표현이다.
• 행렬은 정점과 간선의 정보를 포함한다.
• 각 행렬의 행과 열은 그래프의 정점을 표현한다. 정점이 N개 일 경우, 행렬의 크기는 N*N이 된다.
• 각 정점이 간선으로 연결되어 있을 경우 1로 표현하고, 아닐 경우 0으로 표현한다.

무향 그래프 표현

• 방향이 없기 때문에, 각 정점의 연결이 모두 1로 표현된다.

유향 그래프 표현

• 방향이 있으므로, 1 -> 2 정점 같이 방향에 맞는 정점의 연결만이 1로 표현된다.

가중치 그래프 표현

• 각 간선의 표현을 1이 아니라 가중치로 표현한다.

인접 행렬의 장단점

• 각 행렬의 정점 번호만 주어져도 간선이 있는지 없는지의 여부를 한 번에 확인이 가능하다.
• 하지만 정점의 개수가 N개라면, 간선의 개수에 관계없이 무조건 N*N 만큼의 공간을 차지해야 한다.

---

인접 리스트( Adjency List )

• 인접 리스트는 인접 행렬과 다르게 그래프의 각 정점에서 나가는 간선의 목록을 리스트로 저장하여 표현한다.
• 따라서 각 정점마다 연결 리스트를 하나씩 가지게 된다.

무향 그래프 표현

• 방향이 없으므로, 모든 노드가 인접 리스트를 가진다.
• 각 정점과 연결된 마지막 노드를 표현할 때에는 NULL로 연결하여 표현한다.

유향 그래프 표현

• 무향 그래프와 다르게 정점에서 출발하여 연결되는 정점이 있을 경우에만 인접 리스트로 표현한다.
• 각 인접 리스트의 길이의 합이 간선의 개수가 된다.
• 역시 마지막 노드를 표현할 때에는 링크를 NULL로 연결한다.

가중치 그래프 표현

• 연결 리스트의 노드에 가중치를 포함할 수 있도록 구현한다.

인접 리스트의 장단점

• 정점의 개수와 간선의 개수만큼 O(V+E) 만큼의 공간만 필요하다.
• 인접 리스트는 특정 정점끼리 연결되어있는지 확인하기 위해서 인접 리스트를 모두 순회해야 한다는 단점이 있다.
• O(V^2)보다 O(V+E)가 작은 경우, 메모리 사용면에서 인접 배열보다 이점이 있다.

---

그래프의 구현

https://www.softwaretestinghelp.com/java-graph-tutorial/ 를 참고하여, 각 그래프의 구현과 그래프의 순회인 BFS, DFS에 대해 살펴본다.

인접 행렬 구현

간단하게 배열 형태로 구현해볼 수 있다.

 

인접 리스트 구현

• 인접 리스트는 한 정점에서부터 각 정점까지의 간선을 포함하도록 구현한다.
• 우선 간선의 정보를 담을 클래스를 생성한다.
• 간선 클래스는 출발점, 도착점을 포함할 수 있도록 설정한다.그래프는 해당 간선의 정보를 받아서, 인접 리스트로 표현하도록 한다.

class Edge {
    int src, dst;

    Edge(int src, int dst) {
        this.src = src;
        this.dst = dst;
    }
}

• 각 정점을 기준으로 그 정점이 가지는 인접 리스트에 대한 정보를 Map으로 선언한다.

public class GraphAdjencyList {
    Map<Integer, List<Integer>> adjList = new HashMap();

    public GraphAdjencyList(List<Edge> edges) {
        for (Edge edge : edges) {
            if(adjList.get(edge.src) == null) {
                adjList.put(edge.src, new ArrayList<>());
            }

            adjList.get(edge.src).add(edge.dst);
        }
    }

    public void printGraph() {
        // 0,1,3,4 -> Set
        for(int src : adjList.keySet()) {
            System.out.println("source: " + src);
            for(int dst : adjList.get(src)) {
                System.out.println("\t => " + dst);
            }
        }
    }

    public static void main(String[] args) {
        List<Edge> edges = new ArrayList<>(); // 간선의 정보를 가지는 리스트

        edges.add(new Edge(0, 1));
        edges.add(new Edge(1, 2));
        edges.add(new Edge(0, 2));
        edges.add(new Edge(3, 1));
        edges.add(new Edge(3, 4));
        edges.add(new Edge(4, 0));

        GraphAdjencyList graph = new GraphAdjencyList(edges);
        graph.printGraph();
    }
}

• 가중치를 추가하고 싶다면, Integer에 들어갈 값을 클래스 형태로 변경해주면 된다.

---

그래프의 탐색

• 그래프의 모든 정점을 순서에 따라서 방문하는 탐색 알고리즘이다.
• 그래프의 탐색 방식에는 크게 DFS, BFS 2가지가 존재한다.

깊이 우선 탐색( Depth-First Search )

• 현재 정점과 인접한 간선들을 하나씩 검사하고, 방문하지 않은 간선이 있다면 해당 간선으로 따라가는 방식으로 탐색하게 된다.
• 만약 더 이상 탐색할 정점이 없다면, 왔던 길을 되돌아간다.
• 왔던 길을 되돌아가는 깊이 우선 탐색의 구현에는 크게 2가지 방식이 있을 수 있다.
• 스택을 활용하는 방법과, 재귀를 활용하는 방법이다.

깊이 우선 탐색 - 스택 구현

1. 시작점이 0이라 가정해본다. 0을 방문하고, 0과 인접해있는 노드들을 모두 스택에 넣는다.

2. 스택의 가장 위 3을 꺼낸다. 그리고 3과 인접한 노드들을 모두 스택에 넣는다. 이 과정에서 방문했던 노드는 제외한다. 방문했던 0을 제외

한 방문하지 않은 노드가 없으므로, 바로 맨 위의 값인 2를 스택에서 꺼낸다.

3. 노드 2와 인접해 있으면서 방문하지 않은 노드들을 모두 스택에 넣는다. 4가 스택에 들어가게 된다.

4. 노드 4가 꺼내지게 되고, 마지막으로 1이 꺼내지게 되고 탐색이 완료된다.

5. 출력 결과를 보면 시작점 0에서부터 갈 수 있는 정점까지 쭉 표현되는 것을 확인할 수 있다.

여기서 스택에 들어가 있는 순서에 따라 결과가 0-3-2-4-1로 나왔으나, 스택에 1 2 3의 순서와 같이 반대로 들어가 있었다면 0-1-2-4-3과 같은 결과가 출력되었을 것이다. 하지만 모든 노드가 탐색된다는 것에는 변함이 없다.

 

코드는 다음과 같다.

public class DFS_stack {
    List<List<Integer>> adjList;
    int vertices; // 정점의 개수

    DFS_stack(int vertices) {
        this.vertices = vertices;
        adjList = new ArrayList<>();

        for(int i=0; i<vertices; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    public void addEdges(int src, int dst) {
        adjList.get(src).add(dst);
        adjList.get(dst).add(src);
    }

    public void DFS(int v, Stack<Integer> stack) {
        boolean[] visited = new boolean[v];

        stack = new Stack<>();
        stack.push(v);
        int count = 0;

        while(count < visited.length) {
            v = stack.pop();
            count++;
            visited[v] = true;

            System.out.print(v + " ");

            for(int dst : adjList.get(v)) {
                if(!visited[dst]) {
                    stack.push(dst);
                }
            }
        }
    }

    public static void main(String[] args) {
        DFS_stack graph = new DFS_stack(5);

        graph.addEdges(0, 1);
        graph.addEdges(0 ,2);
        graph.addEdges(0, 3);
        graph.addEdges(2, 4);

        graph.DFS(0, new Stack<>());

        System.out.println();

        graph.DFS(4, new Stack<>());
    }
}

• DFS 스택 구현에서 스택에 들어가 있는 노드들은, 방문 체크가 되어있지 않은 상태이다.
• 스택에서 빠져나와, 방문점으로 간주될 때 방문 체크가 되어야 한다.

---

깊이 우선 탐색 - 재귀 구현

• 재귀 방식의 구현은, 메서드의 방문이 정점의 방문을 의미한다.
• 방문 정점이 가지고 있는 인접 리스트를 순회하면서, 해당 정점이 방문체크가 되어있지 않은 경우 해당 정점으로 메서드를 재귀적으로 호출한다. 만약 메서드가 더 이상 호출되지 않는다면, 재귀가 시작됐던 곳으로 다시 돌아오게 되는 방식이다.

public class DFS_recursive {

    List<List<Integer>> adjList;
    int vertices; // 정점의 개수

    DFS_recursive(int vertices) {
        this.vertices = vertices;
        adjList = new ArrayList<>();

        for(int i=0; i<vertices; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    public void addEdges(int src, int dst) {
        adjList.get(src).add(dst);
        adjList.get(dst).add(src);
    }

    public void DFS(int v, boolean[] visited) {
        visited[v] = true;
        System.out.print(v + " ");

        for(int vtx : adjList.get(v)) {
            if(!visited[vtx]) {
                DFS(vtx, visited);
            }
        }
    }

    public static void main(String[] args) {
        DFS_recursive graph = new DFS_recursive(5);

        graph.addEdges(0, 1);
        graph.addEdges(0 ,2);
        graph.addEdges(0, 3);
        graph.addEdges(2, 4);

        graph.DFS(0, new boolean[5]);

        System.out.println();

        graph.DFS(4, new boolean[5]);
    }
}

너비 우선 탐색( Breadth-First Search )

• 너비 우선 탐색은 인접해 있는 정점부터 순차적으로 방문하여 탐색하는 알고리즘이다.
• DFS와 다르게, BFS에서는 큐를 사용하여 구현할 수 있다.

1. 노드 0부터 큐에 넣고 시작했다고 가정한다. 큐에 0과 인접한 1, 2, 3 노드를 추가한다.

2. 모두 추가하였으면 노드 1을 꺼낸다. 역시 이 과정에서 방문 체크가 되어있지않은 노드들을 큐에 추가한다.

☆ 여기서 DFS 스택 구현과 다른 점이 있다. DFS는 스택에서 나올 때 방문 체크가 되어야 하지만, BFS에서는 큐에 들어갈 때 방문체크가 되어야 한다. 그렇지 않으면 노드 1의 인접 노드들을 체크할 때, 노드 2가 방문했다고 체크되어있지 않기 때문에 중복으로 들어가게 된다.

3. 노드 1의 인접한 노드가 없으므로, 노드 2를 출력하고 인접 노드를 체크한다. 노드 4가 방문하지 않았으므로, 큐에 넣고 방문 체크를 한다.

4. 노드 3, 4를 순차적으로 출력한다.

5. 그래프 출력을 보면 시작점인 노드 0과 인접한 1,2,3 이 출력되고 마지막으로 4가 출력되는 것을 확인할 수 있다.

 

코드는 아래와 같다.

public class BFS {
    List<List<Integer>> adjList;
    int vertices; // 정점의 개수

    BFS(int vertices) {
        this.vertices = vertices;
        adjList = new ArrayList<>();

        for(int i=0; i<vertices; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    public void addEdges(int src, int dst) {
        adjList.get(src).add(dst);
        adjList.get(dst).add(src);
    }

    public void BFS(int v) {
        boolean[] visited = new boolean[vertices];

        LinkedList<Integer> que = new LinkedList<>();

        visited[v] = true;
        que.offer(v);

        while(!que.isEmpty()) {
            v = que.poll();
            System.out.print(v + " ");

            for(int dst : adjList.get(v)) {
                if(!visited[dst]) {
                    visited[dst] = true;
                    que.offer(dst);
                }
            }
        }
    }

    public static void main(String[] args) {
        BFS graph = new BFS(5);

        graph.addEdges(0, 1);
        graph.addEdges(0 ,2);
        graph.addEdges(0, 3);
        graph.addEdges(2, 4);

        graph.BFS(0);
        System.out.println();
        graph.BFS(4);
    }
}

이번 주에는 그래프와 그래프의 탐색 방안에 대해 구현해보았다.

하나씩 그림으로 따라가며 생각해보니 이해가 잘 되는 듯하다. 위에 틀린 코드나 설명이 있을 수도 있으니, 잘못된 부분이 있다면 댓글 부탁드리겠습니다.

 

참조

https://www.softwaretestinghelp.com/java-graph-tutorial/