참고

간단하게 Graph와 Node 클래스를 활용하여 BFS와 DFS의 차이를 최대한 이해하기 쉽게 정리한 영상입니다

---

그래프(공통)

class 그래프{
	class 노드{
    	int 데이터;
        LinkedList<Node> 인접노드;
        boolean 방문;
        
        노드(int 데이터){
        	this.데이터 = 데이터;
            this.인접노드 = new LinkedList<>();
            this.방문 = false;
        }
    }
    
    Node[] 노드들;
    그래프(int size){
    	노드들 = new Node[size];
        for(int i = 0; i < size; i++){
        	노드들[i] = new Node(i); //데이터는 단순히 인덱스
        }
    }
    
    void addEdge(int 데이터1, int 데이터2){
    	Node 노드1 = 노드들[데이터1];
        Node 노드2 = 노드들[데이터2];
        // 노드1, 노드2 서로 연결 함
        if(!노드1.adjacent.contains(노드2)){
        	노드1.adjacent.add(노드2);
        }
        if(!노드2.adjacent.contains(노드1)){
        	노드2.adjacent.add(노드1);
        }
    }
}

DFS와 BFS를 구현하기 전에 미리 그래프와 노드에 대해 정의가 필요합니다.
노드는 데이터, 인접 노드, 방문 여부를 가지며 그래프는 전체 노드들을 가집니다

---

DFS

class 그래프{
	void dfs(){
    	dfs(0);
    }
    void dfs(int index){
    	노드 root = 노드들[index];
        Stack<노드> 스택 = new Stack<>();
        스택.push(root); //루트를 스택에 삽입
        root.marked = true; //방문 표시
        
        while(!스택.isEmpty()){
        	노드 r = 스택.pop();
            for(노드 n : r.adjacent){
            	if(n.방문 == false){
                	n.방문 = true;
                    스택.push(n);
                }
            }
            visit(r);
        }
    }
}

DFS는 다른 DFS와 동일하게 스택을 사용하였습니다. 다른 DFS예시들과도 동일하게 방문여부를 체크하고 확인합니다.

---

BFS

class 그래프{
	void bfs(){
    	bfs(0);
    }
    void bfs(int index){
    	노드 root = 노드들[index];
        Queue<노드> 큐 = new LinkedList<>();
        큐.offer(root);
        root.방문 = true;
        
        while(!큐.isEmpty()){
        	노드 r = 큐.poll();
            for(노드 n : r.adjacent){
            	if(n.방문 == false){
                	n.방문 = true;
                    큐.offer(n);
                }
            }
            visit(r);
        }
    }
}

BFS도 DFS와 로직이 거의 유사합니다. 다만 다른 점은 스택이 아닌 큐를 사용한 것 뿐입니다.