用c++实现拓扑排序问题

拓扑排序是一种基于有向无环图(DAG)的排序算法，它将图中的所有节点排成一条线性序列，使得对于任何的有向边(u,v)，都有u在序列中出现在v的前面。C++实现拓扑排序可以使用深度优先搜索(Depth First Search, DFS)和广度优先搜索(Breadth First Search, BFS)两种方式。

DFS实现拓扑排序的过程如下：
1. 首先遍历所有节点，对于每个未访问过的节点，进行一次DFS。
2. 对于每个节点的DFS过程中，记录其状态为“正在访问”。
3. 如果当前节点的邻居节点存在“正在访问”状态，则说明存在环，拓扑排序失败。
4. 否则，将当前节点状态改为“已访问”，并将其加入结果序列中。

BFS实现拓扑排序的过程如下：
1. 统计每个节点的入度。
2. 将入度为0的节点加入队列。
3. 对于队列中的每个节点，将其邻居节点的入度减1。
4. 如果某个邻居节点的入度减为0，则将其加入队列。
5. 将队列中的节点依次出队，加入结果序列中。

相关问题

使用c++实现拓扑排序

拓扑排序是图论中的一种排序方式，用于对有向无环图 (DAG) 中的顶点进行排序。

在 C 语言中，可以使用邻接表来存储图的数据结构，然后使用入度数组记录每个顶点的入度数，再利用队列实现拓扑排序。

下面是一个简单的实现示例：

#include<stdio.h>
#include<stdlib.h>

#define MAX_VERTEX_NUM 20

int vertex_num, edge_num;
int in_degree[MAX_VERTEX_NUM];
int queue[MAX_VERTEX_NUM];
int head[MAX_VERTEX_NUM], tail;

struct EdgeNode{
    int to;
    int next;
};
struct EdgeNode edges[MAX_VERTEX_NUM];
int edge_num = 0;

void add_edge(int from, int to){
    edges[edge_num].to = to;
    edges[edge_num].next = head[from];
    head[from] = edge_num++;
    in_degree[to]++;
}

void topological_sort(){
    int i, j, k;
    tail = 0;
    for (i = 0; i < vertex_num; i++){
        if (!in_degree[i])
            queue[tail++] = i;
    }
    while (tail){
        int u = queue[--tail];
        printf("%d ", u);
        for (i = head[u]; ~i; i = edges[i].next){
            int v = edges[i].to;
            in_degree[v]--;
            if (!in_degree[v])
                queue[tail++] = v;
        }
    }
}

int main(){
    int i, j, k;
    memset(head, -1, sizeof(head));
    scanf("%d%d", &vertex_num, &edge_num);
    for (i = 0; i < edge_num; i++){
        int from, to;
        scanf("%d%d", &from, &to);
        add_edge(from, to);
    }
    topological_sort();
    return 0;
}

希望这对你有所帮助！

用C++实现用栈的拓扑排序

拓扑排序是对有向图进行排序的一种方法，可以用来解决诸如任务调度等问题。栈可以用来存储入度为0的节点，因此可以用栈来实现拓扑排序。

以下是用C++实现用栈的拓扑排序的示例代码：

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

void topologicalSort(vector<vector<int>>& graph, vector<int>& inDegree) {
    stack<int> s;
    int n = graph.size();
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            s.push(i);
        }
    }
    while (!s.empty()) {
        int cur = s.top();
        s.pop();
        cout << cur << " ";
        for (int next : graph[cur]) {
            inDegree[next]--;
            if (inDegree[next] == 0) {
                s.push(next);
            }
        }
    }
}

int main() {
    vector<vector<int>> graph = {
        {1, 2},
        {3},
        {3},
        {}
    };
    vector<int> inDegree = {0, 1, 1, 2};
    topologicalSort(graph, inDegree); // 输出：0 1 2 3
    return 0;
}

在上面的示例代码中，我们首先遍历所有节点，将入度为0的节点压入栈中。然后，每次从栈中弹出一个节点，输出该节点，并将该节点指向的所有节点的入度减1。如果减1后某个节点的入度为0，则将该节点压入栈中。重复此过程直到栈为空，即可得到拓扑排序的结果。