c++ - 在我的图实现中查找边数并执行拓扑排序

Question

过去几天我一直在致力于图形实现。所有这些对我来说都是新的，并且我陷入了实现的两个部分。我正在从输入文件实现类(class)有向图。从该文件中，我可以确定哪些类(class)是其他类(class)的先决条件。然后，我创建一个有向图，其中类(class)作为节点，边连接作为先决条件的类(class)。我还想找到节点和边的总数，并对图执行拓扑排序(稍后我将向边添加权重)。这是我的实现。

有向图.h

class vertex{
public:

    typedef std::pair<int, vertex*> ve;
    std::vector<ve> adjacency;
    std::string course;
    vertex(std::string c){
        course = c;
    }
};

class Digraph{
public:
    void addVertex(std::string&);
    void addEdge(std::string& from, std::string& to, int cost);
    typedef std::map<std::string, vertex *> vmap;
    vmap work;
    int getNumVertices();
    int getNumEdges();
    void getTopoSort(); 

};

有向图.cpp

void Digraph::addVertex(std::string& course){
    vmap::iterator iter = work.begin();
    iter = work.find(course);
    if(iter == work.end()){
        vertex *v;
        v = new vertex(course);
        work[course] = v;
        return;
    }
}

void Digraph::addEdge(std::string& from, std::string& to, int cost){
    vertex *f = (work.find(from)->second);
    vertex *t = (work.find(to)->second);
    std::pair<int, vertex *> edge = std::make_pair(cost, t);
    f->adjacency.push_back(edge);
}

只需返回 work.size 即可轻松查找节点数。我已经确认这工作正常。我不知道如何返回图中的边数。看起来很简单，但我尝试过的一切都不起作用。其次，我完全不知道如何在此图上执行拓扑排序。如有任何帮助，我们将不胜感激。

Answer 1

一种简单的方法是迭代图中的所有顶点，将它们的邻居计数相加，然后除以二:

int Digraph::getNumEdges(){
     int count = 0;
     for (const auto & v : work) {
         count += v.second->adjacency.size();
     }
     return count / 2;
}

要使用基于范围的 for 循环，您需要使用 c++11。对于 g++，命令行上将是 --std=c++11。

编辑: 我刚刚意识到你有一个有向图，你可能想为每个方向数一个。在这种情况下:不要除以二!

int Digraph::getNumEdges(){
     int count = 0;
     for (const auto & v : work) {
         count += v.second->adjacency.size();
     }
     return count;
}