[자료구조/Java] Graph 검색 DFS, BFS 구현

https://www.youtube.com/watch?v=_hxFgg7TLZQ

 

따르고 싶은 유튜브 선생님이 생겼다..........

 

1. BFS : 넓이 우선 탐색

1) Queue로 구현 가능

시작 노드 하나를 큐에 넣고 시작

→ 큐에서 하나 꺼내고

→ 해당 노드의 자식 노드들을 하나씩 큐에 넣음

→ 처음에 넣은 노드를 출력

→ (큐가 빌 때까지 반복)

 

2. DFS : 깊이 우선 탐색

1) Stack으로 구현 가능

스택에 노드를 하나 넣고 시작

→ 스택에서 노드를 꺼내고

→ 자식 노드들을 넣고

→ 꺼낸 노드를 출력

→ (스택이 빌 때까지 반복)

 

2) 재귀 호출로 구현 가능

노드에 방문하면 우선 출력

→ 자식들을 재귀로 호출

 

내용 정리

import java.util.LinkedList;
import java.util.Iterator;
import java.util.Stack;
import java.util.NoSuchElementException;

class Queue<T>{
}

class Graph{
	class Node{
    	int data;
        // 인접한 노드들과의 관계
        LinkedList<Node> adjacent;
        // 방문했는지 마킹
        boolean marked;
        
        //Node 생성자
        Node (int data){
        	this.data = data;
            this.marked = false;
            adjacent = new LinkedList<Node>();
        }
	}
    
    Node[] nodes; // node들을 저장할 배열
    Graph(int size){
    	nodes = new Node[size];
        for(int i=0; i<size; i++){
        	nodes[i] = new Node(i);
        }
    }
    
    //두 노드의 관계를 저장
    void addEdge(int i1, int i2){
    	Node n1 = nodes[i1];
        Node n2 = nodes[i2];
        
        //상대방이 있는지 확인하고 없으면 추가
        if(!n1.adjacent.contains(n2)){
        	n1.adjacent.add(n2);
        }
        if(!n2.adjacent.contains(n1)){
        	n2.adjacent.add(n1);
        }
    }
    
    /* Stack을 이용한 DFS 구현*/
    void dfs(){
    	dfs(0);
    }
    void dfs(int index){
    	Node root = nodes[index];
        Stack<Node> stack = new Stack<Node>();
        stack.push(root);
        root.marked = true;
        while(!stack.isEmpty()){
        	Node r = stack.pop();
            for(Node n : r.adjacent){
            	if(n.marked == false){
                	n.marked = true;
                    stack.push(n);
                }
            }
            visit(r);
        }
    }
    
    /* 재귀 호출을 이용한 DFS 구현 */
    void dfsR(Node r){
    	if(r==null) return;
        r.marked = true;
        visit(r);
        for(Node n : r.adjacent){
        	if(n.marked == false){
            	dfsR(n);
            }
        }
    }
    
    void dfsR(int index){
    	Node r = nodes[index];
        dfsR(r);
    }
    void dfsR(){
    	dfsR(0);
    }
    
    /* Queue를 이용한 BFS 구현 */
    void bfs(){
    	bfs(0);
    }
    
    void bfs(int index){
    	Node root = nodes[index];
        Queue<Node> queue = new Queue<Node>();
        queue.enqueue(root);
        root.marked = true;
        while(!queue.isEmpty()){
        	Node r = queue.dequeue();
            for(Node n : r.adjacent){
            	if(n.makred == false){
                	n.marked = true;
                    queue.enqueue(n);
                }
            }
            visit(r);
        }
    }
    
    //출력
    void visit(Node n){
    	System.out.print(n.data+" ");
    }
}
/*
  0
 /
1ㅡㅡ3    7
|  / | \ /
| /  |  5
2ㅡㅡ4   \
          6ㅡ8
*/
public class Test{
	public static void main(String[] args){
    	Graph g = new Graph(9);
        g.addEdge(0,1);
        g.addEdge(1,2);
        g.addEdge(1,3);
        g.addEdge(2,4);
        g.addEdge(3,4);
        g.addEdge(3,5);
        g.addEdge(5,6);
        g.addEdge(5,7);
        g.addEdge(6,8);
        g.bfs();
        g.dfs();
        g.dfsR();
    }
}

   

굿^__^!

 

 

문제 유형에 따라 DFS/BFS 구분하기

devuna.tistory.com/32

[알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS)