C++의 너비 우선 검색 미로
너비 우선 검색은 트리 또는 그래프 데이터 구조를 순회하거나 검색하는 알고리즘입니다. 각 노드에서 알고리즘은 부모를 방문하기 전에 자식을 방문합니다.
즉, 부모로 올라가고 자식으로 내려가는 것이 아니라 각 트리 수준의 현재 위치에서 바깥쪽으로 확장됩니다.
너비 우선 탐색은 그래프에서 최단 경로를 찾는 데 사용됩니다. 인공 지능, 컴퓨터 과학, 수학 및 사회 과학과 같은 많은 분야에서 솔루션을 찾는 데 사용되었습니다.
너비 우선 검색 알고리즘
Breadth-first search는 트리를 폭 방향으로 순회하여 폭 우선 방식으로 노드를 확장하는 검색 알고리즘입니다.
알고리즘은 임의의 노드에서 시작하여 모든 자식을 확장합니다. 그런 다음 각 자식에 대해 동일한 작업을 수행하는 식입니다.
프로세스는 리프 노드에 도달하거나 목표 상태를 찾으면 종료됩니다.
한 노드에서 다른 노드까지의 최단 경로를 찾으려면 해당 노드로부터의 거리를 알아야 합니다. 이것은 그래프의 두 노드 사이의 가장자리 길이를 추가하여 계산할 수 있습니다.
C++에서 너비 우선 검색 미로를 수행하는 단계
C++에서 너비 우선 탐색 미로를 수행하는 단계는 다음과 같습니다.
-
그래프 개체를 만들고 가장자리와 정점으로 초기화합니다.
-
너비 우선 검색을 수행할 꼭짓점을 포함하는 대기열을 만듭니다.
-
대기열의 전면 포인터를
NULL로 초기화합니다. -
너비 우선 검색을 수행하려는 정점을 포함하는 빈 목록을 만듭니다.
-
목록의 앞 포인터를
NULL로 초기화합니다. -
자신과 연결된 시작 정점(인덱스가 0인 정점)을 대기열에 추가합니다.
-
목록에 시작 정점을 추가하고 상위 포인터를
NULL로 설정합니다.
큐가 비어 있지 않으면 요소를 가져와 탐색되지 않은 노드에 도달할 때까지 재귀적으로 너비 우선 검색 알고리즘을 호출합니다.
마지막으로 대기열이 비게 되면 미로의 한쪽 끝에 도달하고 해당 방향에서 탐색되지 않은 노드 검색을 중지합니다.
C++에서 너비 우선 탐색 미로의 예
이것은 C++의 너비 우선 탐색 미로의 예입니다. 이 코드는 지정된 시작 노드에서 그래프의 다른 모든 노드까지의 최단 경로를 찾는 알고리즘을 구현합니다.
#include <bits/stdc++.h>
using namespace std;
#define HORI 3
#define VERT 3
struct Point {
int a;
int b;
};
struct queueNode {
Point de;
int sam;
};
bool isValid(int hori, int vert) {
return (hori >= 0) && (hori < HORI) && (vert >= 0) && (vert < VERT);
}
int horiNum[] = {9, 7, 9, 2};
int vertNum[] = {3, 3, 4, 5};
int BFS(int lk[][VERT], Point ace, Point hello) {
if (!lk[ace.a][ace.b] || !lk[hello.a][hello.b]) return -1;
bool visited[HORI][VERT];
memset(visited, false, sizeof visited);
visited[ace.a][ace.b] = true;
queue<queueNode> e;
queueNode s = {ace, 0};
e.push(s);
while (!e.empty()) {
queueNode curr = e.front();
Point de = curr.de;
if (de.a == hello.a && de.b == hello.b) return curr.sam;
e.pop();
for (int i = 0; i < 4; i++) {
int hori = de.a + horiNum[i];
int vert = de.b + vertNum[i];
if (isValid(hori, vert) && lk[hori][vert] && !visited[hori][vert]) {
visited[hori][vert] = true;
queueNode Adjcell = {{hori, vert}, curr.sam + 1};
e.push(Adjcell);
}
}
}
return -1;
}
int main() {
int lk[HORI][VERT] = {{3, 9, 2}, {4, 5, 3}, {0, 3, 0}};
Point source = {0, 0};
Point hello = {1, 1};
int sam = BFS(lk, source, hello);
if (sam != 1)
cout << "Shortest Path:" << sam;
else
cout << "Failed!!!";
return 0;
}
위에서 언급한 코드의 작동을 확인하려면 여기를 클릭하십시오.
Muhammad Adil is a seasoned programmer and writer who has experience in various fields. He has been programming for over 5 years and have always loved the thrill of solving complex problems. He has skilled in PHP, Python, C++, Java, JavaScript, Ruby on Rails, AngularJS, ReactJS, HTML5 and CSS3. He enjoys putting his experience and knowledge into words.
Facebook