그래프(Graph)-너비우선탐색(BFS, Breadth First Search) algorithm

지금까지 그래프란 무엇이고 그래프를 표현하기위한 방법으로 인접행렬과 인접리스트를 알아보았다.

이번에는 그래프의 모든 정점(노드)들을 방문하는 순회(traversal)에 대해서 알아보려고한다.

그래프의 일종인 트리에서도 이미 순회하는 방법을 알아 보았는데 pre-order, in-order, post-order, level-order 가 있었다.

그래프에서는 모든 정점들을 순회하기위한 방법은 여러가지가 있지만 대표적으로 2가지가 있는데 하나는 너비우선탐색(BFS, Breadth First Search)이고 다른 하나는 깊이우선탐색(DFS, Depth First Search)이다.

△ [출처] https://neo4j.com/blog/graph-algorithms-neo4j-graph-algorithm-concepts/

 

먼저 너비우선탐색(BFS, Breadth First Search)을 살펴보고 이어서  깊이우선탐색(DFS, Depth First Search)을 살펴볼 것이다.

너비우선탐색(BFS, Breadth First Search)은 어찌보면 이진트리의 레벨순서순회(level order traversal)과 비슷한 개념이고 큐(Queue)를 이용하여 알고리즘을 구현할 수 있다. 

 

 

△ [출처] https://www.tutorialspoint.com/data_structures_algorithms/breadth_first_traversal.htm

 

위 그림처럼 보면 시작노드 S 가 레벨 0 이라고 하고 레벨1 = { A, B, C }, 레벨2 = { D, E, F } , 레벨3 = { G } 로 이루어져 있다면

위에서 → 아래로,  좌측에서 → 우측으로   레벨 0 부터 레벨 N 까지 방문하지 않은 노드들을 차례로 방문하면 되는것이다.

따라서 방문순서는 S → A → B → C → D → E → F → G 가 된다. 

 

 

BFS를 큐를 이용하여 구현할 수 있다고 하였는데 코드로 직접 구현하기전에 단계별로 어떻게 구현해야할지 살펴보자.

큐를 이용하여 구현할때 3가지 규칙만 명심하면 된다.

 

BFS를 큐를 이용하여 구현시 규칙 3가지

단계 1 - 인접하지 않은 정점중 방문한 적이 없는 정점을  큐에 넣고 방문한 적이 있는것으로 마크(체크)해 놓아라
단계 2 - 만약 인접한 정점이 발견되지 않는다면 큐에서 첫번재 것을 제거해라.
단계 3 - 큐의 사이즈가 0이될때까지(empty) 단계 1, 2 를 반복해라.

이 과정을 그림으로 좀더 자세히 알아보자.

---

처음에 큐는 아무것도 없는 상태이다. 우리는 가장 먼저 방문할 정점이 어떤것인지 결정해야한다. 

여기서는 가장 먼저 S (시작 노드)를 방문하는 것으로 시작하여 방문한 것으로 표시한다.

S 정점과 인접한 노드는 (A,B,C)중  방문한적이 없는 것들을 방문한 것으로 표시하고 큐에다 push 한다.
현재 A,B,C 모두 방문한적이 없기때문에 셋중 한개를 선택해야하는데 알파벳순서로 push 한다면 A를 큐에 추가(enqueue)하고 방문한 것으로 표시한다. 

그 다음에는 S의 인접 노드들중 방문한 적이 없으면서 알파벳순서로 들어갈 것은 B 이기 때문에 B를 큐에 넣고 방문한 것으로 표시한다.

마자찬가지로 다음에는 C를 큐에 추가하고 방문한 것으로 표기한다.

이제 S는 방문하지 않은 어떤 인접한 노드가 없기 때문에 A를 꺼(dequeue)낸다.

A노드에 인접한 노드중 방문하지 안은 노드 D가 있기 때문에 D를 큐에 추가하고 방문한 것으로 표시한다.

마지막으로 큐에 있는것을 하나씩 꺼내면서 인접한 노드들중 방문하지 않은것이 있는지 확인해본다.
여기서는 모두 방문한 적이 있기 때문에 더이상 큐에 추가되지 못하고 최종적으로 큐의 사이즈가 0 이 된다.

 

 
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.function.Consumer;
 
/**
 * 인접리스트를 사용해 그래프 구현.
 * */
public class AdjListGraph {
 
    private static final String NEWLINE = System.getProperty("line.separator");
    private final int V;
    private int E;
    private ArrayList<LinkedList<Integer>> adj;
 
    public AdjListGraph(int V) {
        if (V < 0) throw new IllegalArgumentException("Number of vertices must be nonnegative");
        this.V = V;
        this.E = 0;
 
        // 정점 집합을 표현하는 하나의 배열과 각 정점마다 인접한 정점들을 연결리스트로 추가하기위한 연결리스트를 생성한다.
        adj = new ArrayList<>(V);
        for (int v = 0; v < V; v++) {
            adj.add(new LinkedList<Integer>());
        }
    }
 
    // 정점의 개수를 리턴.
    public int V() {
        return V;
    }
 
    // 에지의 개수를 리턴
    public int E() {
        return E;
    }
 
 
    // vertext 는 초기에 지정된 사이즈보다 크거나 0보다 작으면 안된다.
    private void validateVertex(int v) {
        if (v < 0 || v >= V)
            throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
    }
 
    public void addEdge(int v, int w) {
        validateVertex(v);
        validateVertex(w);
        E++;
 
        adj.get(v).add(w);
        // 무방향 그래프이니 반대도 추가해야한다
        adj.get(w).add(v);
    }
 
 
    // 정점의 인접리스트를 리턴한다.
    public Iterable<Integer> adj(int v) {
        validateVertex(v);
        return adj.get(v);
    }
 
 
    // 정점과 연결된 인접리스트(edge) 개수를 리턴한다.
    public int degree(int v) {
        validateVertex(v);
        return adj.get(v).size();
    }
 
    // 너비우선 탐색 알고리즘
    public static void bfs(AdjListGraph graph, int s, Consumer<Integer> consumer) {
        Queue<Integer> q = new ArrayDeque<>();
        // 방문한적이 있는지 체크하기위한 변수
        boolean[] marked = new boolean[graph.V()];
 
        // 처음 시작이 s 부터 이므로 s는 방문한 적이 있는것으로 마크해놓고 큐에 enqueue 한다.
        marked[s] = true;
        q.offer(s);
 
        while(!q.isEmpty()) {
            int v = q.poll();
            consumer.accept(v);
            for(int w : graph.adj(v)) {
                // 큐에서 뺀 정점이 방문한적이 없는 노드가 있으면 큐에 추가해준다.
                if (!marked[w]) {
                    marked[w] = true;
                    q.offer(w);
                }
            }
        }
    }
 
    public String toString() {
        StringBuilder s = new StringBuilder();
        s.append(V + " vertices, " + E + " edges " + NEWLINE);
        for (int v = 0; v < V; v++) {
            s.append(v + ": ");
            for (int w : adj.get(v)) {
                s.append(w + " ");
            }
            s.append(NEWLINE);
        }
        return s.toString();
    }
 
 
}
 
 
public class Main {
 
    public static void main(String[] args)  {
        AdjListGraph graph = new AdjListGraph(9);
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);
        graph.addEdge(2, 5);
        graph.addEdge(3, 5);
        graph.addEdge(3, 7);
        graph.addEdge(3, 8);
        graph.addEdge(5, 6);
        graph.addEdge(7, 8);
 
        // output : 1 2 3 4 5 7 8 6 
        AdjListGraph.bfs(graph, 1, (i) -> {
            System.out.print(i + " ");
        });
 
    }
 
 
}

BFS 알고리즘 출력 순서는 처음 시작하는 노드가 무엇인지에 따라 출력은 다를수 있다.

BFS 알고리즘은 순회(traversal) 외에 출발지점(S)부터 각 정점(vertext)까지의 최단경로(shortest path)를 계산하는데에도 이용할수 있는데 여기서는 가중치가 없는 그래프이므로 S  → 모든 노드 V에 대한 최단경로는 경로의 길이 즉, 에지의 개수가 될 것이다.

 

위코드에서 모든 노드 V에 대한 최단경로를 구하기위해서는 살짝 코드를 바꾸어야 하는데

출발지점 S 로부터 V까지의 최단경로의 길이(에지의 개수)를 저장하기 위한 distTo[] 와 S로 부터 V까지의 최단경로상에서 V의 직전 노드(predecessor)를 저장하기 위한 edgeTo[] 가 필요하다.

이전 AdjListGraph 내에 있었던 bfs 함수에 최단경로를 위한 기능을 추가 하기 위한 BFS 클래스 코드이다.

 
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;
import java.util.function.Consumer;
 
public class BFS {
    private static final int INFINITY = Integer.MAX_VALUE;
 
    private AdjListGraph graph;
    private Queue<Integer> q = new ArrayDeque<>();
    // 방문한적이 있는지 체크하기위한 변수
    private boolean[] marked ;
    // 출발 S 로부터 V까지 최단경로상에서 V의 직전노드(predecessor)
    private int[] edgeTo ;
 
    // 출발 S 로부터 V까지 최단경로 길이
    private int[] distTo ;
 
    public BFS(AdjListGraph graph, int s) {
        marked = new boolean[graph.V()];
        edgeTo  = new int[graph.V()];
        distTo  = new int[graph.V()];
        this.graph = graph;
 
    }
 
    // 너비우선 탐색 알고리즘
    public  void bfs(int s, Consumer<Integer> consumer) {
 
        // 처음 시작이 s 부터 이므로 s는 방문한 적이 있는것으로 마크해놓고 큐에 enqueue 한다.
        for (int v = 0; v < graph.V(); v++)
            distTo[v] = INFINITY;
 
        distTo[s] = 0;
        marked[s] = true;
 
        q.offer(s);
 
        while(!q.isEmpty()) {
            int v = q.poll();
            consumer.accept(v);
            for(int w : graph.adj(v)) {
                // 큐에서 뺀 정점이 방문한적이 없는 노드가 있으면 큐에 추가해준다.
                if (!marked[w]) {
                    edgeTo[w] = v;
                    distTo[w] = distTo[v] + 1;
                    marked[w] = true;
                    q.offer(w);
                }
            }
        }
    }
 
    // 출발 지점부터 노드 v 까지 최단거리를 리턴.
    public int distTo(int v) {
        validateVertex(v);
        return distTo[v];
    }
 
    // 출발 지점부터 노드 v 까지 최단거리(path)가 있으면 true, 없으면 false
    public boolean hasPathTo(int v) {
        validateVertex(v);
        return marked[v];
    }
 
    // 출발지점부터 v 까지 최단거리리 정점 목록들으 리턴한다.
    public Iterable<Integer> pathTo(int v) {
        validateVertex(v);
 
        if (!hasPathTo(v)) return null;
        Stack<Integer> path = new Stack<Integer>();
 
        int x;
        for (x = v; distTo[x] != 0; x = edgeTo[x]) {
            path.push(x);
        }
        path.push(x);
        return path;
    }
 
 
 
    private void validateVertex(int v) {
        int V = marked.length;
        if (v < 0 || v >= V)
            throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
    }
}
 
 
public class Main {
 
    public static void main(String[] args)  {
        AdjListGraph graph = new AdjListGraph(9);
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);
        graph.addEdge(2, 5);
        graph.addEdge(3, 5);
        graph.addEdge(3, 7);
        graph.addEdge(3, 8);
        graph.addEdge(5, 6);
        graph.addEdge(7, 8);
 
 
        BFS bfs = new BFS(graph, 1);
        bfs.bfs(1, (i) -> System.out.print(i + " "));
        System.out.println("-----");
        // 7 3 1 
        for(int i : bfs.pathTo(7)) {
            System.out.print(i + " ");
        }
 
    }
 
 
}

아래 메소드는 bfs 출발지점이 여러개인경우도 가능하게 변경한 코드이다. 

 private void bfs(Iterable<Integer> sources , Consumer<Integer> consumer) {
        Queue<Integer> q = new ArrayDeque<>();
        for (int s : sources) {
            marked[s] = true;
            distTo[s] = 0;
            q.offer(s);
        }
        while (!q.isEmpty()) {
            int v = q.poll();
            for (int w : graph.adj(v)) {
                if (!marked[w]) {
                    edgeTo[w] = v;
                    distTo[w] = distTo[v] + 1;
                    marked[w] = true;
                    q.offer(w);
                }
            }
        }
    }