拓扑图排序实现问题：编译通过但ordering向量未填充

我正在实现拓扑图排序，程序能正常编译，但存储排序结果的ordering向量始终未被填充。用调试工具追踪变量也没找到原因。

我的图数据结构定义如下：

class 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;
    // 假设size是Graph类的成员变量，代表顶点数量
};

所有结构已在图生成阶段完成初始化。

以下是我实现的排序代码：

void Graph::myOwnOrderingHelper(int v, bool *visited, std::stack<std::vector<vertex*>> &Stack) {

    std::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);
            std::cout << vertices[v].next->id;
            hope.push_back(vertices[v].next);
        }
    }

    Stack.push(hope);
}

void Graph::myOwnOrdering() {
    std:: stack<std::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++){
            std::cout << temp[i]->degree << std::endl;
            ordering.push_back(temp[i]);
        }

        Stack.pop();
    }

}

问题根源分析 #

你的代码存在几个关键错误，直接导致ordering向量为空：

• 邻接节点获取错误：循环中把当前顶点的id赋值给neighbour，完全没拿到真正的邻接节点；同时遍历次数依赖degree，却没有遍历该顶点的邻接边列表。
• 递归参数错误：递归调用时传入循环计数器i，而非邻接节点的索引，逻辑完全错误。
• 入栈逻辑错误：标准DFS拓扑排序是递归结束后将当前顶点入栈，你却试图添加next指针指向的顶点，且因前面的错误，hope向量几乎为空，最终栈里都是空元素，ordering自然无法被填充。

修复后的代码 #

以下是符合标准DFS拓扑排序逻辑的修正代码：

// 修正后的递归辅助函数
void Graph::myOwnOrderingHelper(int v, bool *visited, std::stack<vertex*> &Stack) {
    visited[v] = true;

    // 正确遍历当前顶点的邻接边列表
    Edge* currentEdge = edges[v];
    while (currentEdge != nullptr) {
        int neighbour = currentEdge->dest;
        if (!visited[neighbour]) {
            myOwnOrderingHelper(neighbour, visited, Stack);
        }
        currentEdge = currentEdge->next;
    }

    // 递归完成后将当前顶点压入栈
    Stack.push(&vertices[v]);
}

// 修正后的主排序函数
void Graph::myOwnOrdering() {
    std::stack<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]){
            myOwnOrderingHelper(i, visited, Stack);
        }
    }

    // 将栈中元素弹出存入ordering，得到拓扑序
    ordering.clear();
    while (!Stack.empty()){
        ordering.push_back(Stack.top());
        Stack.pop();
    }

    delete[] visited; // 释放动态分配的内存
}

额外说明 #

• 确保edges数组已正确初始化，edges[v]指向顶点v的邻接边列表头节点。
• vertex结构体的next/previous指针是用于顶点集合的链表管理，和邻接表逻辑无关，注意不要混淆。
• 标准DFS拓扑排序逻辑：访问完当前节点的所有邻接节点后，将当前节点压入栈，最终栈的弹出顺序即为拓扑排序结果。

内容的提问来源于stack exchange，提问作者Nicole Sood