Graph | 너비 우선 탐색(Breadth-First Search)

1. BFS와 DFS란?

대표적인 그래프 탐색 알고리즘 

 * 너비 우선 탐색(Breadth First Search) : 정점들과 같은 레벨에 있는 노드들(형제 노드들)을 먼저 탐색하는 방식

 * 깊이 우선 탐색(Depth First Search) : 정점의 자식들을 먼저 탐색하는 방식 

 

2. Java로 그래프를 표현하는 방법

Java Collection Framework에서 제공하는 Hashmap과 ArrayList를 활용해서 그래프를 표현할 수 있음 

그래프 예와 Java 표현 

HashMap<String, ArrayList<String>> graph = new HashMap<String, ArrayList<String>>();

graph.put("A", new ArrayList<String>(Arrays.asList("B", "C")));

// 등등

3. BFS 알고리즘 구현

자료구조 큐를 활용한

 * needVisit 큐와 visited 큐, 두 개의 큐를 생성 

큐의 구성은 간단히 ArrayList 클래스를 활용 

 

BFS 코드 구현 

각각의 알고리즘에서 자료구조가 사용됨을 이해할 수 있음(BFS 에서는 큐 자료구조 사용)

각 자료구조는 자료구조 시간에, 변수/조건문/반복문을 기반으로 밑바닥부터 구현하는 코드도 익힘 

 

public class BFSSearch {
	public ArrayList<String> bfsFunc(HashMap<String, ArrayList<String>> graph, String startNode) {
    	ArrayList<String> visited = new ArrayList<String>();
        ArrayList<String> needVisit = new ArrayList<String>();
        
        neetVisit.add(startNode);
        
        while(needVisit.size() > 0){ 
        	String node = needVisit.remove(0);
            
            if(!visited.contains(node)) {
            	visited.add(node);
                needVisit.addAll(graph.get(node));
            }
        }
        
        return visited;
    }
}

4. 시간 복잡도

O(V(노드 수) + E(간선 수))