编辑代码

#include <iostream>
#include <vector>
#include <queue>
#include <string>

using namespace std;

// 定义图的最大顶点数
const int MAX_VERTEX_NUM = 7;

// 图的邻接表存储结构
class Graph {
private:
    vector<string> vertex;  // 存储顶点信息
    vector<vector<int>> adjList;  // 邻接表
    vector<bool> visited;  // 记录顶点是否被访问过

public:
    Graph() {
        vertex.resize(MAX_VERTEX_NUM);
        adjList.resize(MAX_VERTEX_NUM);
        visited.resize(MAX_VERTEX_NUM, false);
    }

    // 初始化图
    void initGraph() {
        vertex[0] = "A";
        vertex[1] = "B";
        vertex[2] = "C";
        vertex[3] = "D";
        vertex[4] = "E";
        vertex[5] = "F";
        vertex[6] = "G";

        adjList[0] = {1, 2};
        adjList[1] = {0, 3};
        adjList[2] = {0, 4};
        adjList[3] = {1, 5};
        adjList[4] = {2, 5};
        adjList[5] = {3, 4, 6};
        adjList[6] = {5};
    }

    // 广度优先搜索算法
   void BFS(int start, int end) {
    queue<vector<int>> q;  // 存储路径的队列
    q.push({start});
    visited[start] = true;

    while (!q.empty()) {
        vector<int> currentPath = q.front();
        q.pop();
        int current = currentPath.back();

        if (current == end) {
            cout << "找到路径: ";
            for (int node : currentPath) {
                cout << vertex[node] << " ";
            }
            cout << endl;
            continue;  // 继续搜索其他路径
        }

        for (int neighbor : adjList[current]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                vector<int> newPath = currentPath;
                newPath.push_back(neighbor);
                q.push(newPath);
            }
        }
    }

    // 重置 visited 数组（如果需要多次调用 BFS）
    fill(visited.begin(), visited.end(), false);
}
int main() {
    Graph graph;
    graph.initGraph();
    graph.BFS(0, 6);  // 从起点A（索引0）到终点G（索引6）进行BFS搜索
    return 0;
}