shortest path1 [BFS] 너비 우선 탐색 BFS (너비 우선 탐색) 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘 각 정점을 방문할 때마다 모든 인접 정점을 검사합니다. 처음 보는 정점을 발견하면 이 점을 방문 예정(discoverd)이라고 기록한 뒤, 별도의 위치(queue)에 저장합니다. 인접한 정점을 모두 검사하고 나면, 저장한 목록에서 다음 정점을 꺼내서 방문합니다. BFS (너비 우선 탐색)에서 새 정점을 발견하는데 사용했던 간선을 모은 트리를 BFS Spanning Tree(너비 우선 탐색 신장 트리) 라고 부릅니다. #include #include using namespace std; // Adjacent List vector adj; vector order; /* start 노드로부터 시작하여 너비 우선 탐색하여 각 .. 2019. 9. 9. 728x90 이전 1 다음
