[자료구조] 그래프 탐색

그래프 탐색

 

1. DFS (깊이 우선 탐색)

 

• 각 노드를 방문했는지 체크할 배열과 스택을 이용하여 구현

// 인접행렬 ver.
public void dfs(int id) {
    boolean[] visited = new boolean[this.elemCnt];
    Stack<Integer> stack = new Stack<>();

    stack.push(id);
    visited[id] = true;

    while (!stack.isEmpty()) {
        int tmp = stack.pop();
        System.out.print(this.vertices[tmp] + " ");

        for (int i = 0; i < this.elemCnt; i++) {
            if (!visited[i] && this.adjMat[tmp][i] == 1) {
                visited[i] = true;
                stack.push(i);
            }
        }
    }
}

 

// 인접 리스트 ver.
public void dfs(int id) {
    boolean[] visited = new boolean[this.elemCnt];
    Stack<Integer> stack = new Stack<>();

    stack.push(id);
    visited[id] = true;
    
    while (!stack.isEmpty()) {
        int tmp = stack.pop();
        System.out.println(this.vertices[tmp] + " ");

        Node cur = this.adjList[tmp];
        while (cur != null) {
            if (!visited[cur.id]) {
                stack.push(cur.id);
                visited[cur.id] = true;
            }
            cur = cur.next;
        }
    }
    System.out.println();
}

 

 

2. BFS (너비 우선 탐색)

 

• 각 노드를 방문했는지 체크할 배열과 큐를 이용하여 구현

// 인접행렬 ver.
public void bfs(int id) {
    boolean[] visited  = new boolean[this.elemCnt];

    Queue<Integer> queue = new LinkedList<>();
    
    queue.offer(id);
    visited[id] = true;
    while (!queue.isEmpty()) {
        int tmp = queue.poll();
        System.out.print(this.vertices[tmp] + " ");
        
        for (int i = 0; i < this.elemCnt; i++) {
            if (!visited[i] && this.adjMat[tmp][i] == 1) {
                queue.offer(i);
                visited[i] = true;
            }
        }
    }
    System.out.println();
}

 

// 인접 리스트 ver.
public void bfs(int id) {
    boolean[] visited = new boolean[this.elemCnt];
    Queue<Integer> queue = new LinkedList<>();

    queue.offer(id);
    visited[id] = true;

    while (!queue.isEmpty()) {
        int tmp = queue.poll();
        System.out.println(this.vertices[tmp] + " ");

        Node cur = this.adjList[tmp];
        while (cur != null) {
            if (!visited[cur.id]) {
                queue.offer(cur.id);
                visited[cur.id] = true;
            }
            cur = cur.next;
        }
    }
    System.out.println();
}