c++ - 这个拓扑排序算法的复杂度是 O(P+D)，其中 P 是项目，D 是依赖关系？

Question

我已经用 C++ 编写了一个拓扑排序算法，但我不确定复杂度是否达到应有的水平。我知道有一种拓扑排序算法可以在 O(P+D) 时间内工作，其中 p 是项目，D 是依赖项的数量，但我不确定我是否正确编写了它。你能看看吗？代码如下。也欢迎任何其他改进建议，我觉得有 2 个相邻列表效率低下，我认为应该有更好的方法来做到这一点。

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

using namespace std;

class Graph
{
public:
    Graph(vector<string> projects, vector<pair<string,string>> dependencies)
    {   
        int counter=0;
        for(int i=0;i< projects.size();i++)
        {
            strToInt[projects[i]]=counter++;    
        }
        adjList.resize(projects.size());
        for(int i=0;i<dependencies.size();i++)
        {
            adjList[strToInt[dependencies[i].second]].first.insert(strToInt[dependencies[i].first]);
            adjList[strToInt[dependencies[i].first]].second.push_back(strToInt[dependencies[i].second]);
        }
    }

    vector<pair<unordered_set<int>,vector<int>>> adjList;
    unordered_map<string,int> strToInt;

    bool BuildOrder(){
        vector<int> visited(adjList.size(),0);
        queue<int> q;
        int count =0;
        for(int i=0;i<adjList.size();i++)
        {
            if(adjList[i].first.size()==0)
            {
                count++;
                q.push(i);
            }
        }
        while(!q.empty())
        {
            count++;
            int temp=q.front();
            q.pop();
            visited[temp]=1;
            for(int i=0;i<adjList[temp].second.size();i++)
            {
                adjList[i].first.erase(temp);
                if(adjList[i].first.size()==0&&visited[i]==0)
                {
                    q.push(i);
                }
            }
        }
        if(count==visited.size())
        {
            return true;
        }
        return false;
    }

};

int main()
{
    vector<string> projects {"a", "b", "c", "d", "e", "f"};
    vector<pair<string,string>> dependencies{
        {"a","d"},
        {"f","b"},
        {"b","d"},
        {"f","a"},
        {"d","c"}
    };
    Graph g(projects,dependencies);
    bool temp=g.BuildOrder();
    return 0;
}

Answer 1

我不完全理解您的代码在做什么，但我认为它正在实现 Kahn 的算法。 Kahn 算法的问题在于它需要一个图形表示，您可以在其中有效地获得有向图中给定顶点的近邻和外邻。对我来说，考虑到一种拓扑类型自然地脱离了仅对外邻的深度优先搜索，这使得它太麻烦了。

下面是DFS方式的一个实现。我用两个访问过的集合来做，就像他们在维基百科文章中解释的那样，因为这样你甚至不需要跟踪图的源顶点，在构建图时入度为零的顶点——尽管如果你知道基于 DFS 的算法的来源更简单。

#include <iostream>
#include <iterator>
#include <functional>
#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <deque>

using Edges = std::vector<std::pair<std::string, std::string>>;
using Vertices = std::vector<std::string>;
using Graph = std::unordered_map<std::string, std::vector<std::string>>;

Graph BuildAjacencyList(const Edges& edges)
{
    Graph graph;
    for (const auto& edge : edges)
        graph[edge.first].push_back(edge.second);
    return graph;
}

Vertices FindTopologicalOrder(const Vertices& vertices, const Edges& edges)
{
    auto graph = BuildAjacencyList(edges);

    std::unordered_set<std::string> unexplored, visited;
    std::copy(vertices.begin(), vertices.end(), std::inserter(unexplored, unexplored.end()));

    std::deque<std::string> topo_order;
    std::function<bool(std::string)> visit = [&](std::string vert) {
        if (unexplored.find(vert) == unexplored.end())
            return true;
        if (visited.find(vert) != visited.end())
            return false;
        visited.insert(vert);
        for (const auto& neighbor : graph[vert])
            if (!visit(neighbor))
                return false;
        visited.erase(vert);
        unexplored.erase(vert);
        topo_order.push_front(vert);
        return true;
    };

    while (!unexplored.empty())
        if (!visit(*unexplored.begin()))
            return Vertices(); // the dependency graph has a cycle.

    return Vertices(topo_order.begin(), topo_order.end());
}

int main()
{
    std::vector<std::string> projects{ "a", "b", "c", "d", "e", "f" };
    Edges dependencies{
        {"a","d"},
        {"f","b"},
        {"b","d"},
        {"f","a"},
        {"d","c"},
        {"b","e"}
    };

    auto order = FindTopologicalOrder(projects, dependencies);
    if (order.empty()) {
        std::cout << "there is a cycle in these dependencies\n";
    } else {
        for (const auto& vert : order)
            std::cout << vert << std::endl;
    }
    return 0;
}