BFS

Breadth First Search

너비 우선 탐색 : 정점들과 같은 레벨에 있는 노드들을 먼저 탐색하는 방식

구현

• 자료구조 큐를 활용
  • need_visit 큐와 visited 큐
  • 처음 두개의 큐는 비어있다
  • need_visit에 첫 노드를 전달해 주면서 시작

public static void main(String[] args) {
	Dictionary<Character, List<Character>> graph = new Hashtable<>();
	graph.put('A', List.of('B', 'C'));
	graph.put('B', List.of('A', 'D'));
	graph.put('C', List.of('A', 'G', 'H', 'I'));
	graph.put('D', List.of('B', 'E', 'F'));
	graph.put('E', List.of('D'));
	graph.put('F', List.of('D'));
	graph.put('G', List.of('C'));
	graph.put('H', List.of('C'));
	graph.put('I', List.of('C', 'J'));
	graph.put('J', List.of('I'));

	BFS(graph, 'A').forEach(s -> System.out.print(s+" "));
}
private static Queue<Character> BFS(Dictionary<Character, List<Character>> graph, Character start)
{
    Queue<Character> needVisit = new LinkedList<>();
    Queue<Character> visited = new LinkedList<>();

    needVisit.add(start);
    int count = 0;
    while (!needVisit.isEmpty())
    {
        count += 1;
        Character now = needVisit.poll();
        if (!visited.contains(now)) {
            visited.add(now);
            needVisit.addAll(graph.get(now));
        }
    }
    System.out.println(count);
    return visited;
}
//출력
19
A B C D G H I E F J 

시간 복잡도

노드 수 : V
간선 수 : E
시간 복잡도 : O(V + E)