将图形表示为 unordered_map<string, vector<string>> 时出现拓扑排序错误

Question

当我尝试在 C++ 中使用表示图的 unordered_map<string, vector<string>> 实现拓扑排序时，我遇到了一个无法解释的错误（从我这方面来说）。具体来说，当被访问的 'current node' 不作为键存在于 unordered_map 中时（即它没有传出边），这种情况仅发生。它没有返回 'correct' 订单，而是完全终止函数调用 topSort 并且 returns 只是订单的一小部分。

代码returns：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";
}

Answer 1

插入 unordered_map 会使个迭代器无效到映射 if it rehashes 中。这会用 auto elem : graph 打破你的循环（顺便说一下，它会复制你的 vector<string> 对象；使用 auto &elem 代替）。将您的图表作为 const& 传递以避免此类恶作剧；然后编译器会温和地建议您使用 at 而不是 operator[].

将图形表示为 unordered_map<string, vector<string>> 时出现拓扑排序错误

Error in topological sort when representing the graph as an unordered_map<string, vector<string>>

c++

depth-first-search

unordered-map

topological-sort