这是使用模板的图形的标准BFS算法。该算法适用于除字符串之外的所有基本数据类型。我知道这是当空值传递给 std::string(( 时引起的,但我无法确切地弄清楚为什么代码中首先应该有一个空字符串。
#include <bits/stdc++.h>
using namespace std;
template < typename T >
class Graph {
unordered_map < T, list < T >> adjList;
public:
void addEdge(T u, T v, bool birdir = true) {
adjList[u].push_back(v);
if (birdir)
adjList[v].push_back(u);
}
void printG() {
for (auto i: adjList) {
cout << i.first << "->";
for (auto nodes: i.second) {
cout << nodes << ",";
}
cout << endl;
}
}
void BFS(T src) {
queue < T > Q;
unordered_map < T, bool > visited;
Q.push(src);
//Q.push(nullptr);
visited[src] = true;
while (!Q.empty()) {
T f = Q.front();
Q.pop();
cout << f << " -- ";
for (auto neighbor: adjList[f]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
Q.push(neighbor);
}
}
}
}
};
int main() {
Graph < string > * g = new Graph < string > ();
g - > addEdge("0", "1", false);
g - > addEdge("1", "3");
//g->printG();
cout << endl;
g - > BFS(0);
}
这里的问题是你如何称呼BFS
。 你使用
g - > BFS(0);
它试图从0
构建一个std::string
. 0
是空指针常量,由于std::string
具有需要const char*
的重载,因此编译器调用该构造函数。 但是,这样做是无效的,因为指针不能是空指针。 这会导致您遇到异常。 您需要将代码更改为
g - > BFS("");
甚至更简单
g - > BFS();
Graph<std::string>::BFS
是一个接受std::string
的成员函数。调用 g->BFS(0);
时,0
用于构造 std::string
参数,并调用采用const char*
的构造函数。这称为std::string::string(nullptr)
.
若要避免0
在 gcc 中的代码中被解释为空指针,请使用 -Wzero-as-null-pointer-constant
。你可能的意思是g->BFS("0")
(字符串"0"
(