好的，我必须对图进行拓扑排序算法。我需要找到度数为0的节点并将其排入队列，然后将其打印并删除去往它的所有边缘。我通过减少countList映射中进入边缘的数量来删除边缘。我将邻接列表作为地图，将每个节点的度数作为地图。我的算法仅访问邻接表的第一个元素。因此我的输出队列仅显示邻接列表的第一个关键字。一遍又一遍。我在25处停止了while循环，因此它不会是无限的。
string z = "";
string a = "";
cout << "Queue: ";
do{
for(it = countList.begin(); it!=countList.end(); ++it){
if(it->second == 0){
Q.push(it->first);
countList.at(it->first)--;
z = adjList[it->first];
cout <<"z: " << z <<endl;
//remove edges
for(int i = 0; i< z.length(); i++){
a = z.at(i);
cout << "z at " <<i << " : " <<a <<endl;
countList.at(a)--;
}//end for
}//end if
//cout << Q.front() << ", ";
//Q.pop();
}//end for
cout << Q.front() << ", ";
Q.pop();
}while(!Q.empty());
有人可以帮助我理解为什么它没有遍历countList而是只停留在第一个元素上吗？
谢谢。
因此，我将countList.at（a）-+ 1更改为countList.at（a）-以进行适当的减量。
现在，输出不仅仅是角度为0的第一个顶点。但是输出仍然是错误的。
这就是全部。
我的变量声明
vector<string> E;
map<string, string> adjList;
map<string, int>countList;
map<string, int>::iterator it;
queue<string> Q;
我不想为adjacencyList或countList编写代码，但是这是它们的外观。
//These represent the edges between the two paired nodes
AdjacencyList: (1,2) (1,4) (1,3) (2,4) (2,5) (3,6) (4,6) (4,7) (4,3) (5,4) (5,7) (7,6)
//The first is the node name and the second element is how many edges come into that node.
countList: (1,0) (2,1) (3,2) (4,3) (5,1) (6,3) (7,2)
我的输出应该是：
Queue: 1,2,5,4,3,7,6
//or
Queue: 1,2,5,4,7,3,6
好的，我添加了
countList.at（it-> first）-;
在将顶点推入队列后。因此，应该将该顶点的计数减为-1。
这使我的输出范围大大缩小。
现在就可以了！！！
我将while循环更改为在队列为空后停止，并在while循环中打印了队列，从而解决了该问题。
我的输出现在是：
Queue: 1, 2, 5, 4, 7, 3, 6,
好的，仅当节点名称仅为单个值时，此代码才有效。
如何更改节点名称长于单个字符的值的adjList映射？
也许键值指向一个链表？如果是这样，我该怎么做？
最佳答案
好吧，现在我们到了某个地方。
第一个版本（在您进行编辑之前）确实错误地减少了传入的边缘计数。
现在还有另一个问题：在每次迭代中，您都重复获取已经被占用的节点（节点＃1是一个很好的示例），因为它们的计数仍然为零（传入边的数量）。通过一次又一次地减少其祖先，某些计数将降至零以下（例如对于节点2）。
您必须以某种方式标记已使用的节点，并且不要在每个周期中一次又一次地使用它们。这可以通过以下方法实现：a）通过为节点设置一些标志，b）使用一组使用的节点，c）通过从列表中删除该节点，或者（可能是最简单的）d）通过将其边缘计数设置为负数来实现将它们放入输出队列后的数字（例如-1）。
在您进行第二次编辑后，这样的算法应该可以工作（在短短的两周后对我有效）。但是，adjList的用法很奇怪-您如何在一个映射中准确地包含一个节点的多个边？
关于c++ - 拓扑排序算法无法正常工作，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/22920925/