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

Question

最近几天我一直在研究图形实现。所有这些对我来说都是全新的，我被困在我的实施的两个部分。我正在从输入文件中实现课程的有向图。从文件中，我可以确定哪些课程是其他课程的先决条件。然后我创建了一个有向图，其中课程作为节点，边缘连接作为先决条件的课程。我还想找到节点和边的总数，并对图执行拓扑排序（稍后我将向边添加权重）。这是我的实现。

Digraph.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(); 

};

Digraph.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);
}

只需 return work.size 即可轻松找到节点数。我已经确认这是正常工作的。我不知道如何 return 我的图中的边数。看起来很简单，但我尝试的一切都不起作用。其次，我完全不知道如何对该图进行拓扑排序。感谢任何帮助。

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;
}

Answer 2

首先，对于边的数量，在构建图时直接计算它们会更简单（只需在有向图中添加一个计数器 class 并在每次添加边时递增它......）

对于拓扑排序，首先我有一个问题：你的边是从prereqs到dependent courses？如果 A 是 B 的先决条件，那你有一个 link A -> B 吗？如果不是这种情况，您需要反转您的图表。

您了解主要算法以构建拓扑排序：一个基于您的顶点（在您的案例中是课程）的简单 DFS (http://en.wikipedia.org/wiki/Depth-first_search) and the other relying on in-degrees (http://en.wikipedia.org/wiki/Directed_graph#Indegree_and_outdegree)

通常情况下，您需要验证您的图形不包含任何循环，如果您的数据是连贯的，通常会出现这种情况。

让我们考虑基于 DFS 的算法：DFS 从给定的根开始遍历出现的边之后的每个顶点。我们可以很容易地证明，顶点最后一次相遇的顺序形成了一个逆拓扑顺序。所以，我们只需要在调用其后继节点后将当前顶点压入堆栈即可。

我再次使用 C++11 为您做了一个快速而肮脏的实现。

首先，将以下内容添加到 Digraph class：

  typedef std::unordered_set<vertex*> marks_set;
  marks_set marks;
  typedef std::deque<vertex*> stack;
  stack topo;
  void dfs(vertex* vcur);

然后是代码：

void Digraph::dfs(vertex* vcur) {
  marks.insert(vcur);
  for (const auto & adj : vcur->adjacency) {
    vertex* suc = adj.second;
    if (marks.find(suc) == marks.end()) {
      this->dfs(suc);
    } // you can detect cycle in the else statement
  }
  topo.push_back(vcur);
}

void Digraph::getTopoSort() {
  // It should be a good idea to separate this algorithm from the graph itself
  // You probably don't want the inner state of it in your graph,
  // but that's your part.

  // Be sure marks and topo are empty
  marks.clear();
  topo.clear();
  // Run the DFS on all connected components
  for (const auto & v : work) {
    if (marks.find(v.second) == marks.end()) {
      this->dfs(v.second);
    }
  }
  // Display it
  for (const auto v : topo) {
    std::cout << v->course << "\n";
  }
}

代码可以编译，但我还没有测试。如果出于任何原因您对递归算法（函数 Digraph::dfs）有疑问，可以使用包含目标顶点父节点和迭代器的堆栈 去递归化当前后继者，迭代器到达邻接表的末尾，可以在拓扑排序中推父。

另一个算法几乎一样简单：对于每个顶点，您需要计算前驱的数量（度数），这可以在构建图形时完成。为了计算拓扑排序，您寻找入度为 0 的第一个顶点（没有前任），然后减少其所有后继的入度并继续下一个为 0 的顶点。如果图有没有循环，总会有一个入度为 0 的顶点（当然在开始时，但也在算法运行期间随着你减少它）直到所有顶点都被看到。顶点相遇顺序形成拓扑排序（这与Bellman最短路径算法有关。）

请注意，此处列出了这 2 个算法：http://en.wikipedia.org/wiki/Topological_sorting。使用入度的方法是根据 删除边缘 来描述的，我们只是通过降低入度来模拟（一种破坏性小得多的方法……）

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

Finding the number of edges and performing a topo sort in my graph implementation

c++

graph

graph-algorithm

topological-sort