그래프 탐색 - DFS와 BFS

DFS

자료형 : 스택

구현 : 재귀, 백트래킹

한 사람이 미로를 빠져나감

Pre-order traversal

1. Visit node
2. Traverse left
3. Traverse right

preorder(node)
	if node == null then return
	visit(node)
	preorder(node.left)
  preorder(node.right)

In-order traversal

1. Traverse left
2. Visit node
3. Traverse right

inorder(node)
	if node == null then return
	inorder(node.left)
	visit(node)
	inorder(node.right)

Post-order traversal

1. Traverse left
2. Traverse right
3. Visit node

postorder(node)
	if node == null then return
	postorder(node.left)
	postorder(node.right)
	visit(node)

BFS

자료형 : 큐

여러 사람이 서로 다른 길로 미로를 빠져나감

Level-order traversal

levelorder(root)
	q <- empty queue
	q.enqueue(root)
	while (not q.isEmpty())
		node <- q.dequeue()
		visit(node)
		if (node.left != null)
			q.enqueue(node.left)
    if (node.right != null)
    	q.enqueue(node.right)

다익스트라 알고리즘

시간복잡도 : $O(^2)$, 우선순위 큐 사용시 $O(V+E)$, 모든 정점이 출발지에서 도달 가능하면 $O(E\log(V))$

Reference

• Tree traversal : MIchael Sambol