graph2 너비 우선 탐색 BFS 알고리즘 - 그래프 탐색 너비 우선 탐색 (BFS)으로 그래프를 탐색해보자. 그래프 탐색 하나의 정점으로 시작하여, 차례대로 모든 정점을 한 번씩 방문하는 것이다. 특정 도시에서 다른 도시로 갈 수 있는지 없는지, 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지 알아볼 수 있다. 너비 우선 탐색 BFS BFS는 그래프에서 넓게 우선적으로 탐색하는 알고리즘이다. 깊이 우선 탐색 (DFS)은 스택(stack)을 사용하지만, 너비 우선 탐색 (BFS)은 큐(queue)를 사용한다. 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 사용한다. DFS보다 빠르지만 복잡하다. 어떤 노드를 방문했는지 검사해야한다. BFS의 동작 방식 자신과 인접한 노드를 전부 queue에 넣는다. queue에 들어있는 노드들을 .. 2021. 9. 11. 깊이 우선 탐색 DFS 알고리즘 - 그래프 탐색 깊이 우선 탐색(DFS)으로 그래프를 탐색해보자. 그래프 탐색 하나의 정점으로 시작하여, 차례대로 모든 정점을 한 번씩 방문하는 것이다. 특정 도시에서 다른 도시로 갈 수 있는지 없는지, 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지 알아볼 수 있다. 깊이 우선 탐색 DFS DFS는 탐색에서 깊은 것을 우선적으로 탐색하는 알고리즘이다. 너비 우선 탐색 (BFS)는 큐(queue)가 사용되지만, 깊이 우선 탐색 (DFS)는 스택(stack)이 사용된다. 사실 컴퓨터는 함수 호출을 스택의 원리를 사용하기 때문에, 재귀를 사용하면 DFS를 구현할 수 있다. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다. 모든 경우의 수를 보기 좋다! BFS보다는 속도가 느리다. 어떤 노드를 방문했는지 검사하.. 2021. 9. 11. 이전 1 다음
