|
无向图有 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;
}
|
|