首页 文章

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

提问于
浏览 次
2

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

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

找到节点数很容易就返回 work.size . 我已经确认这是正常的 . 我迷失了如何返回图表中的边数 . 看起来这很简单，但我尝试的一切都行不通 . 其次，我完全迷失了如何在此图上执行拓扑排序 . 任何帮助表示赞赏 .

c++ graph graph-algorithm topological-sort

2 回答

  • 3

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

    对于拓扑排序，首先我有一个问题：你的边缘是从先决条件到从属课程？如果A是B的先决条件，那么你有一个链接A - > B.如果不是这种情况，则需要反转图形 .

    您可以使用main算法来构建拓扑排序：一个基于简单的DFS（http://en.wikipedia.org/wiki/Depth-first_search），另一个基于顶点的入度（http://en.wikipedia.org/wiki/Directed_graph#Indegree_and_outdegree）（在您的情况下为课程） .

    通常，您需要验证图表是否包含任何周期，如果您的数据一致，通常就是这种情况 .

    让我们考虑基于DFS的算法：DFS在出现时沿着边缘遍历给定根的每个顶点 . 我们可以很容易地证明顶点的最后一次遇到的顺序形成了反向拓扑顺序 . 所以，我们需要的是在对其后继者的调用之后将当前顶点推入堆栈 .

    我再次使用C 11为你做了一个快速而又脏的实现 .

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

    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）的问题，可以使用包含目标顶点的父级和当前后继的迭代器的堆栈来解除它，迭代器到达结束时邻接列表，您可以在拓扑排序中推送父级 .

    另一种算法几乎一样简单：对于每个顶点，您需要计算在构建图形时可以完成的前任（in-degree）的数量 . 为了计算拓扑排序，你寻找第一个具有in-degree 0（没有前任）的顶点，然后减少其所有后继的in-degree，并继续使用0的下一个顶点 . 如果图表有没有循环，总会有一个度数为0的顶点（当然，在算法运行期间，当你减少它时），直到看到所有顶点 . 顶点的顺序形成拓扑排序（这与Bellman最短路径算法有关 . ）

    请注意，这里列出了这两种算法：http://en.wikipedia.org/wiki/Topological_sorting . 使用in-degree的一个用删除边来描述，我们通过减少in-degree简单地模拟（一个破坏性较小的方法......）

    回复于
  • 1

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

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

    要使用基于for循环的范围，您需要使用c 11.使用命令行中的 --std=c++11 .

    EDIT: 我刚刚意识到你有一个有向图，你可能想要为每个方向计算一个 . 在这种情况下：不要除以2！

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

相关问题