>  기사  >  백엔드 개발  >  C++에서 너비 우선 검색 알고리즘을 사용하는 방법

C++에서 너비 우선 검색 알고리즘을 사용하는 방법

WBOY
WBOY원래의
2023-09-19 16:49:47822검색

C++에서 너비 우선 검색 알고리즘을 사용하는 방법

C++에서 너비 우선 탐색 알고리즘을 사용하세요

폭 우선 탐색 알고리즘(BFS)은 그래프의 시작점에서 시작하여 대상 노드까지 각 노드를 순차적으로 방문하고 탐색하는 그래프 탐색 알고리즘입니다. 또는 전체 그림이 발견되었습니다. BFS는 대기열을 사용하여 구현됩니다. 먼저 시작 노드가 대기열에 추가된 다음 대기열이 빌 때까지 인접한 노드가 대기열에 추가됩니다.

다음은 C++를 사용하여 너비 우선 검색 알고리즘을 구현하는 샘플 코드입니다.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// 图的节点
struct Node {
    int id;
    bool visited;
    vector<Node*> neighbors;
    Node(int _id) : id(_id), visited(false) {}
};

// 广度优先搜索算法
void BFS(Node* start) {
    // 使用队列保存要访问的节点
    queue<Node*> q;
    // 标记起点已经被访问
    start->visited = true;
    q.push(start);

    while (!q.empty()) {
        Node* current = q.front();
        q.pop();
        cout << current->id << " ";

        // 遍历当前节点的相邻节点
        for (Node* neighbor : current->neighbors) {
            // 如果相邻节点未被访问,则标记为已访问并入队
            if (!neighbor->visited) {
                neighbor->visited = true;
                q.push(neighbor);
            }
        }
    }
}

int main() {
    // 创建图的节点
    Node* A = new Node(1);
    Node* B = new Node(2);
    Node* C = new Node(3);
    Node* D = new Node(4);
    Node* E = new Node(5);

    // 构建节点之间的连接关系
    A->neighbors.push_back(B);
    A->neighbors.push_back(C);
    B->neighbors.push_back(A);
    B->neighbors.push_back(D);
    C->neighbors.push_back(A);
    C->neighbors.push_back(D);
    D->neighbors.push_back(B);
    D->neighbors.push_back(C);
    D->neighbors.push_back(E);
    E->neighbors.push_back(D);

    // 从节点A开始进行广度优先搜索
    cout << "BFS traversal starting from node A: ";
    BFS(A);

    return 0;
}

위 코드에서는 먼저 그래프의 노드 구조를 정의합니다. Node,其中包含节点的ID、是否访问过和相邻节点的指针列表。然后,我们实现了广度优先搜索算法BFS,使用队列来保存要访问的节点。在每次循环中,我们取出队列的首个节点,将其ID输出,并遍历其相邻节点,将未被访问过的节点加入队列中。最后,在main함수에서 간단한 그래프를 만들고 너비를 시작합니다. 먼저 노드 A 검색에서.

이 샘플 코드를 통해 C++의 너비 우선 검색 알고리즘을 이해하고 사용하여 그래프에서 연결된 노드를 찾고 최단 경로 및 기타 문제를 해결하여 다양한 실제 시나리오에 적용할 수 있습니다.

위 내용은 C++에서 너비 우선 검색 알고리즘을 사용하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명:
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.