面试题：C++ 深度优先搜索在拓扑排序中的应用

Question

给定一个有向无环图（DAG），以邻接矩阵的形式给出。请使用C++ 通过深度优先搜索实现拓扑排序。你需要考虑如何处理节点访问状态，以及如何保证排序结果的正确性。图的邻接矩阵定义如下： ```cpp using namespace std; const int N = 100; int graph[N][N]; ```

Answer 1

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

const int N = 100;
int graph[N][N];
vector<bool> visited(N, false);
stack<int> topoOrder;

void dfs(int node) {
    visited[node] = true;
    for (int i = 0; i < N; ++i) {
        if (graph[node][i] &&!visited[i]) {
            dfs(i);
        }
    }
    topoOrder.push(node);
}

vector<int> topologicalSort() {
    for (int i = 0; i < N; ++i) {
        if (!visited[i]) {
            dfs(i);
        }
    }
    vector<int> result;
    while (!topoOrder.empty()) {
        result.push_back(topoOrder.top());
        topoOrder.pop();
    }
    return result;
}

1. 节点访问状态处理：通过一个visited数组来记录每个节点是否被访问过，初始时所有节点都标记为未访问。
2. 保证排序结果正确性：
   • 在dfs函数中，先将当前节点标记为已访问，然后递归访问其所有未访问的邻接节点。
   • 当一个节点及其所有邻接节点都被访问完毕后，将该节点压入栈中。这样，栈中元素的顺序就是拓扑排序的逆序。
   • 最后将栈中的元素依次弹出，得到的就是拓扑排序的结果。由于有向无环图的特性，这样的排序是正确的。

你可以使用以下方式调用上述函数：

int main() {
    // 假设已经给graph赋值
    vector<int> topo = topologicalSort();
    for (int i : topo) {
        cout << i << " ";
    }
    cout << endl;
    return 0;
}