gpt4 book ai didi

c++ - 将图形表示为unordered_map >时,拓扑排序错误

转载 作者:行者123 更新时间:2023-12-02 10:21:38 26 4
gpt4 key购买 nike

当我尝试使用代表图形的unordered_map<string, vector<string>>在C++中实现拓 flutter 排序时,遇到了无法解释的错误(就我而言)。具体而言,当正在访问的“当前节点”不作为unordered_map中的键存在(即,它没有传出边沿)时,仅在时才发生。它没有返回“正确”的顺序,而是完全终止了函数调用topSort,并且仅返回该顺序的一小部分。

代码返回:ML, AML, DL
相反,可能的正确解决方案可能是:LA, MT, MA, PT, ML, AML, DL
谁能解释为什么会这样?

下面是发生问题的一个小代码段:

// 0 -> white (node has not been visited)
// 1 -> grey (node is currently being visited)
// 2 -> black (node is completely explored)
bool topSortVisit(unordered_map<string, vector<string>>& graph,
unordered_map<string, int>& visited, string node, vector<string>& result){

if(visited[node] == 1) return false;
if(visited[node] == 2) return true;

// Mark current node as being visited.
visited[node] = 1;
// node might not have outgoing edges and therefore not in the
// unordered_map (graph) as a key.
for(auto neighbor : graph[node]){
if(!topSortVisit(graph, visited, neighbor, result)) return false;
}

result.push_back(node);
visited[node] = 2;
return true;
}

vector<string> topSort(unordered_map<string, vector<string>>& graph){

unordered_map<string, int> visited;
vector<string> result;

// Should visit all nodes with outgoing edges in the graph.
for(auto elem : graph){
string node = elem.first;
bool acyclic = topSortVisit(graph, visited, node, result);
if(!acyclic){
cout << "cycle detected\n";
return vector<string>{};
}

}

reverse(result.begin(), result.end());
return result;
}

这里是重现一切的代码:
#include<iostream>
#include<vector>
#include<unordered_map>
#include<algorithm>

using namespace std;

bool topSortVisit(unordered_map<string, vector<string>>& graph,
unordered_map<string, int>& visited, string node, vector<string>& result){

if(visited[node] == 1) return false;
if(visited[node] == 2) return true;

visited[node] = 1;
for(auto neighbor : graph[node]){
if(!topSortVisit(graph, visited, neighbor, result)) return false;
}

result.push_back(node);
visited[node] = 2;
return true;
}

vector<string> topSort(unordered_map<string, vector<string>>& graph){

unordered_map<string, int> visited;
vector<string> result;

for(auto elem : graph){
string node = elem.first;
bool acyclic = topSortVisit(graph, visited, node, result);
if(!acyclic){
cout << "cycle detected\n";
return vector<string>{};
}

}

return result;
}


unordered_map<string, vector<string>> makeGraph(vector<pair<string, string>> courses){
unordered_map<string, vector<string>> graph;

for(auto p : courses){
graph[p.first].push_back(p.second);
}
return graph;
}

int main(){

vector<pair<string, string>> pairs;
pairs.push_back(make_pair("LA", "ML"));
pairs.push_back(make_pair("MT", "ML"));
pairs.push_back(make_pair("MA", "PT"));
pairs.push_back(make_pair("PT", "ML"));
pairs.push_back(make_pair("ML", "DL"));
pairs.push_back(make_pair("ML", "AML"));

auto graph = makeGraph(pairs);
vector<string> result = topSort(graph); // ML, AML, DL
// A possible correct solution could be: LA, MT, MA, PT, ML, AML, DL


for(string s : result){
cout << s << " ";
}
cout << "\n";
}

最佳答案

unordered_map中插入会使 map if it rehashes中的迭代器无效。这就破坏了您与auto elem : graph的循环(顺便说一句,它复制了vector<string>对象;改为使用auto &elem)。将您的图形作为const&传递,以避免这种恶作剧;然后,编译器会轻轻建议您使用at而不是operator[]

关于c++ - 将图形表示为unordered_map <string,vector <string >>时,拓扑排序错误,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59896613/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com