Published on

그래프 탐색 - DFS와 BFS

Authors
  • avatar
    Name
    Indo Yoon
    Twitter
Table of Contents

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(^2), 우선순위 큐 사용시 O(V+E)O(V+E), 모든 정점이 출발지에서 도달 가능하면 O(Elog⁡(V))O(E\log(V))

Reference

Discuss on Twitter • View on GitHub