我正在尝试实现一个拓扑图排序,我的程序正在编译,但是我没有得到一个填充向量。我已经尝试运行调试器来跟踪我的变量去哪里,我不太确定为什么。目前,我已经做了一个图形数据结构,它包含一个顶点向量。这是在我生成一个新图形时生成的(std::向量顶点;)
我的图是这样的结构:
lass Graph {
struct Edge{
int dest = -1;
Edge* next = nullptr;
Edge(int dest, Edge* next) : dest(dest), next(next){};
~Edge() {delete next;}
};
struct vertex{
int id =0;
int degree = 0;
int colour = 0;
vertex* next = nullptr;
vertex* previous = nullptr;
};
Edge** edges = nullptr;
std:: vector<vertex> vertices;
std:: vector<vertex*> ordering;
所有这些都是在图形生成过程中设置的。
我真的很感激任何帮助与此排序。
void Graph::myOwnOrderingHelper(int v, bool *visited, std::stack<vector<vertex*>> &Stack) {
vector<vertex*> hope;
visited[v] = true;
for (int i = 0; i < vertices[v].degree; i++) {
int neighbour = vertices[v].id;
if (!visited[neighbour]){
myOwnOrderingHelper(i, visited, Stack);
cout << vertices[v].next->id;
hope.push_back(vertices[v].next);
}
}
Stack.push(hope);
}
void Graph::myOwnOrdering() {
std:: stack<vector<vertex*>> Stack;
bool* visited = new bool[size];
for(int i = 0; i < size; i++){
visited[i] = false;
}
for (int i = 0; i < size; i++){
if (visited[i] == false){
myOwnOrderingHelper(i, visited, Stack);
}
}
while (Stack.empty() == false){
std::vector<vertex*> temp = Stack.top();
for(int i = 0; i < temp.size(); i++){
cout << temp[i]->degree << endl;
ordering.push_back(temp[i]);
}
Stack.pop();
}
}
2条答案
按热度按时间rt4zxlrg1#
看看这个代码:
每次通过这个for循环,
neighbour
的值总是相同的。无论你的for循环要完成什么(你的代码没有文档记录,所以不容易猜测),它实际上总是一遍又一遍地做完全相同的事情。
dly7yett2#
这里有一些不必要的复杂性,使算法变得模糊不清。
有了它,就可以通过添加6行来实现拓扑排序。
提示:当你在一个你可以控制输入数据的小程序中遇到意想不到的行为时,添加跟踪打印
cerr << ...
通常比设置调试器更容易,特别是当你是编程新手的时候。