DFS

Depth First Search

깊이 우선 탐색 : 정점의 자식들을 먼저 탐색하는 방식

구현

• 자료구조 스택과 큐를 활용
  • needVisit스택과 visited 큐를 사용

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

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

시간복잡도

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