BSF算法

一起看海

无向图有 24 个顶点，分别用 A'、B、C'、D'、E'、F'、G'、H'、I'、J'、K'、L'、M'、N'、P'、Q'、R'、S'、T'、U'、V'、W'、Y' 和 Z' 表示。{M'， Z'}， {M'， Y'}， {L'， W'}， {K'， V'}， {J'， U'}， {J'， T'}， {I'， S'}， {H'， R'}， {G'， Q'}， {F'， P'}， {F'， N'}， {E'， M'}， {E'， L'}， {D'， K'}， {D'， J'}， {D'， I'}， {C'， H'}， {C'， G'}， {B'， F'}， {B'， E'}， {A'， D'}， {A'， C'}， 和 {A'， B'} 是此图中的边。假设广度优先搜索不会沿任何路径重新访问任何顶点。每条边等价于两个算子，例如，{A'， B'}对应的算子是A' --> B'和B' --> A'。如果 D' 是初始状态，V' 是目标状态，那么除了 D' 和 V' 之外，有多少个顶点是广度优先搜索保证访问的？
我已经编写了以下代码，但我对一件事感到困惑。我是否应该考虑 D 的近邻，包括 A、I、J 和 K，并考虑所有可能性？
假设
可以从 D、I、J 和 K 访问，然后从 I 访问“S”，从 J、“T”和“U”访问，从“K”访问“V”。到目前为止，{E，J，K，S，T，U} 都在这边访问。现在我的问题是，我是否也应该考虑通过 A 的所有路径？就像 B 和 C 可以通过 A 访问一样，那么 E 和 F 可以通过 B 访问，到目前为止，依此类推。非常感谢您的帮助。

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

using namespace std;

unordered_map<char, vector<char>> graph = {
    {'A', {'B', 'C', 'D'}},
    {'B', {'A', 'F', 'E'}},
    {'C', {'A', 'H', 'G'}},
    {'D', {'A', 'K', 'J', 'I'}},
    {'E', {'B', 'M', 'L'}},
    {'F', {'B', 'P', 'N'}},
    {'G', {'C', 'Q'}},
    {'H', {'C', 'R'}},
    {'I', {'D', 'S'}},
    {'J', {'D', 'T', 'U'}},
    {'K', {'D', 'V'}},
    {'L', {'E', 'W'}},
    {'M', {'E', 'Z', 'Y'}},
    {'N', {'F'}},
    {'P', {'F'}},
    {'Q', {'G'}},
    {'R', {'H'}},
    {'S', {'I'}},
    {'T', {'J'}},
    {'U', {'J'}},
    {'V', {'K'}},
    {'W', {'L'}},
    {'Y', {'M'}},
    {'Z', {'M'}}
};

int bfs(char start, char goal) {
    queue<vector<char>> q;
    unordered_map<char, bool> visited;
    q.push({ start });
    visited[start] = true;

    while (!q.empty()) {
        vector<char> path = q.front();
        q.pop();
        char node = path.back();

        if (node == goal) {
            cout << "Shortest path: ";
            for (char vertex : path) {
                cout << vertex << " -> ";
            }
            cout << "\b\b\b   \n";
            return path.size() - 1;
        }

        for (char adjacent : graph[node]) {
            if (!visited[adjacent]) {
                visited[adjacent] = true;
                vector<char> new_path = path;
                new_path.push_back(adjacent);
                q.push(new_path);
            }
        }
    }

    return -1;
}

int main() {
    char start = 'Z';
    char goal = 'C';

    int operators = bfs(start, goal);
    if (operators != -1) {
        cout << "Number of operators on the path found by BFS: " << operators << endl;
    }
    else {
        cout << "Goal state not reachable from the initial state!" << endl;
    }

    return 0;
}