그래프 탐색 DFS, BFS

인접리스트로 구현된 그래프에서의 구현

package graph;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class ListGraph implements Graph{
    int size;
    boolean directed;
    LinkedList<Integer>[] adj;
    LinkedList<Integer>[] inv;

    public ListGraph(int size, boolean directed) {
        this.size = size;           // vertex의 수
        this.directed = directed;   // true: 방향성 그래프, false: 무방향성 그래프
        adj = new LinkedList[size];
        inv = new LinkedList[size];
        for(int i = 0; i < size; i++) {
            adj[i] = new LinkedList<Integer>();
            inv[i] = new LinkedList<Integer>();
        }
    }
    
    ... 중략
    
    private void dfs(int v, List<Integer> L, boolean[] visited) {
        visited[v] = true;
        L.add(v);
        for(int k:adj[v]) {
            if(!visited[k])
                dfs(k,L,visited);
        }
    }

    public Iterable<Integer> dfs(int v) {
        List<Integer> L = new ArrayList<Integer>(size);
        boolean[] visited = new boolean[size];
        dfs(v,L,visited);
        return L;
    }

    public Iterable<Integer> bfs(int v) {
        List<Integer> L = new ArrayList<Integer>(size);
        boolean[] visited = new boolean[size];
        ArrayDeque<Integer> queue = new ArrayDeque<>(size);
        visited[v] = true;
        L.add(v);
        queue.addLast(v);
        while(!queue.isEmpty()) {
            int k = queue.pollFirst();
            for(int w: adj[k]) {
                if (!visited[w]) {
                    L.add(w);
                    visited[w] = true;
                    queue.addLast(w);
                }
            }
        }
        return L;
    }

    public boolean connected() {
        List<Integer> L = new ArrayList<Integer>(size);
        boolean[] visited = new boolean[size];
        dfs(0,L,visited);
        return L.size() == this.size;   // 그래프가 연결되어있다면 dfs 결과, 모든 vertex를 방문한다.
    }

    public void connectedComponent() {
        List<Integer> L = new ArrayList<Integer>(size);
        boolean[] visited = new boolean[size];
        int count = 0;
        for(int i = 0; i < size; i++) {
            if(!visited[i]) {
                System.out.print("연결 요소 " + count + ": " );
                dfs(i,L,visited);
                for(int k : L) {
                    System.out.print(k+" ");
                }
                System.out.println();
                L.clear();
                count += 1;
            }
        }
    }
}

 

인접행렬로 구현된 그래프에서의 구현

package graph;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

public class MatrixGraph implements Graph{
    int size;
    boolean directed;
    int[][] adj;

    public MatrixGraph(int size, boolean directed) {
        this.size = size;
        this.directed = directed;
        adj = new int[size][size];
    }


	... 중략

    private void dfs(int v, List<Integer> L, boolean[] visited) {
        visited[v] = true;
        L.add(v);
        for(int k = 0; k < size ; k++) {
            if(!visited[k] && adj[v][k]==1)
                dfs(k,L,visited);
        }
    }

    public Iterable<Integer> dfs(int v) {
        List<Integer> L = new ArrayList<Integer>(size);
        boolean[] visited = new boolean[size];
        dfs(v,L,visited);
        return L;
    }

    public Iterable<Integer> bfs(int v) {
        List<Integer> L = new ArrayList<Integer>(size);
        boolean[] visited = new boolean[size];
        ArrayDeque<Integer> queue = new ArrayDeque<>(size);
        visited[v] = true;
        L.add(v);
        queue.addLast(v);
        while(!queue.isEmpty()) {
            int k = queue.pollFirst();
            for(int w = 0; w < size ; w++) {
                if (!visited[w] && adj[k][w]==1) {
                    L.add(w);
                    visited[w] = true;
                    queue.addLast(w);
                }
            }
        }
        return L;
    }
}

 

연습 문제

https://www.acmicpc.net/workbook/view/18082

문제집: 자유 그래프 탐색 DFS BFS (기본) (haus)

https://www.acmicpc.net/workbook/view/18083

문제집: BFS 그래프 탐색 (심화) (haus)