[Java] BFS vs DFS

- AdjMatrix를 활용한 BFS vs DFS

 

bfs 코드

public static void bfs(int cur) {
    ArrayDeque<Integer> queue = new ArrayDeque<>();
    queue.offer(cur);
    visited[cur] = true;			// 큐에 넣을 때 방문 체크 하기!

    while(!queue.isEmpty()) {
        cur = queue.poll();

        // 큐에서 추출한 노드를 처리하기
        System.out.printf("%c -> ", cur + 65);

        // 인접 노드 탐색하기
        for(int i = 0; i < N; i++) {
            // 인접했고, 방문 체크
            if(map[cur][i] && !visited[i]) {
                visited[i] = true;
                queue.offer(i);
            }
        }
    }
}

 

dfs 코드

public static void dfs(int cur) {
    visited[cur] = true;			// call stack 을 사용하므로 함수 호출이 stack 에서 정점을 꺼내기

    System.out.printf("%c -> ", cur+65);

    // 인접 노드 방문하기
    for(int i = 0; i < N; i++) {
        if(map[cur][i] && !visited[i]) {
            dfs(i);
        }
    }
}

 

 

 

- AdjList를 활용한 BFS vs DFS

입력받기

V = sc.nextInt();
E = sc.nextInt();

Node[] adjList = new Node[V];

for(int i = 0; i < E; i++) {
    int from = sc.nextInt();
    int to = sc.nextInt();
    adjList[from] = new Node(to, adjList[from]);
    adjList[to] = new Node(from, adjList[to]);
}

 

bfs 코드

public static void bfs(Node[] adjList, int start) {
    ArrayDeque<Integer> queue = new ArrayDeque<>();
    boolean[] visited = new boolean[V];


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

    while(!queue.isEmpty()) {
        int current = queue.poll();		// 탐색해야 하는 정점 꺼내기

        // 탐색 정점에 관련된 로직 처리 부분
        System.out.printf("%c -> ", current + 65);

        // 인접 정점들 탐색하기
        for(Node temp = adjList[current]; temp != null; temp = temp.next) {
            // 인접했고, 방문 체크
            if(!visited[temp.to]) {
                queue.offer(temp.to);
                visited[temp.to] = true;
            }
        }
    }
}

 

 

 

2024-02-20 수정 필