728x90 반응형 DFS1 BFS와 DFS 너비 우선 탐색(BFS , Breadth-First Search) 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법 사용하는 경우 : 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 선택 ex) A,B사이에 존재하는 경로를 찾는 경우, A에서 가까운 곳 부터 탐색 그래프 탐색의 경우, 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다. -> 이를 검사하지 않을 경우, 무한루프에 빠질 위험이 있다. BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료구조인 큐를 사용한다. ->프림과 다익스트라 알고리즘과 유사하다. BFS(G,k) q.push(G.root) root.visit = true while !q.isEmpty() node r = q.fron.. 2019. 5. 2. 이전 1 다음 728x90 반응형