DFS, BFS - 자바 구현

DFS 깊이우선탐색: 재귀, 스택

BFS 넓이우선탐색: 큐

 

package practice;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

import org.junit.Test;


public class Main {
    private boolean[] visited = new boolean[9];
    
    // (0인덱스는 제외) 각 인덱스 번호가 노드의 번호, 배열 내 원소는 연결된 노드 번호
    // ex: 노드1에 연결된 노드 번호는 2,3,8 
    private int[][] graph = 
    	{{}, {2,3,8}, {1,6,8}, {1,5}, {5,7}, {3,4,7}, {2}, {4,5}, {1,2}};
    //node num: 1        2       3      4       5      6     7      8
    
    private static Stack<Integer> stack = new Stack<>();
    
    //함수 호출용 main Test 함수 
	@Test
	public void testMain() {
//	    dfsSelf(1); // 1 2 6 8 3 5 4 7
//	    dfsSelfStack(1);
	    System.out.println(bfsQueueCustom(1, graph, visited));
	}
	
	//재귀 dfs
	public void dfsSelf(int node) {
	    
	    visited[node] = true; //노드 1 방문 처리
	    
	    System.out.print(node + "-> ");
	    
	    for (int branch: graph[node]) { //노드1의 연결 노드들 탐색
	        if (!(visited[branch])) { //미방문 이라면
	            dfsSelf(branch); //재귀호출
	        }
	    }
	}
	
	 
	//재귀와 스택 dfs
	public void dfsSelfStack(int node) {
	    
	   stack.push(node); // 노드 1 push
       visited[node] = true; // 노드 1 방문 처리
       System.out.print(node + " -> ");

	    while (!stack.isEmpty()) {
	        int nodeIndex = stack.pop(); //노드 1 pop
	        
	        for (int LinkedNode: graph[nodeIndex]) { // 노드1에 연결된 노드들 탐색
	            if (!visited[LinkedNode]) { //미방문 이라면
	                dfsSelfStack(LinkedNode); //재귀호출
	            }
	        }
	    }
	}
	
	//Stack 반복만을 하용한 Main Test 함수 (DFS)
    @Test
    public void stackMain() {
        
    	// 반복 전 초기 처리 
        stack.push(1); //노드 1 push
        visited[1] = true; //노드 1 방문 처리
        
        // stack 이 빌때 까지 반복
        while (!stack.isEmpty()) {
            
            int nodeIndex = stack.pop(); //노드 1 pop
            System.out.print(nodeIndex + " -> ");

            for (int LinkedNode : graph[nodeIndex]) {
                if(!visited[LinkedNode]) {
                    stack.push(LinkedNode); // 다음 노드 push
                    visited[LinkedNode] = true; // 다음 노드 방문 처리 후 로직 재시작          
                }
            }
        }
    }   
    
    //큐 bfs
    public String bfsQueueCustom(int start, int[][] graph, boolean[] visited) {
        StringBuilder sb = new StringBuilder(); // 탐색 순서를 담을 stringBuilder
        Queue<Integer> q = new LinkedList<Integer>();
        
        // 반복 전 최초 처리
        q.offer(start); // 노드 1 offer
        visited[start] = true; // 노드 1 방문 처리
        
        //큐가 빌때까지 반복
        while(!q.isEmpty()) {
            int nodeIndex = q.poll(); //노드 1 (head) 제거 
            sb.append(nodeIndex + "->");
            
            //큐에서 꺼낸 노드(head)에 연결된 노드들 탐색
            for (int LinkedNode: graph[nodeIndex]) {
                if (!visited[LinkedNode]) {
                    q.offer(LinkedNode);
                    visited[LinkedNode] = true; // 다음 노드 방문 처리 
                }
            }
            
        }
        //queue: head tail
        // 1 2 3 8 6 5 4 7
        return sb.toString() ;
    }
}