用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++编写实现拓扑排序非递归算法

在C++中，我们可以使用邻接表（Adjacency List）的数据结构来实现拓扑排序的非递归算法。拓扑排序主要用于有向无环图（DAG，Directed Acyclic Graph）中，对节点进行线性排列，使得所有的边都是从前面的节点指向后面的节点。

下面是一个简单的非递归算法步骤：

1. 使用哈希表存储每个节点的入度（in-degree），记录有多少条边进入该节点。
2. 遍历图，将所有入度为0的节点加入到结果列表中，并将其出度减1（即减少依赖项）。
3. 对于剩下的节点，如果它们的入度仍然为0，继续加入结果列表。
4. 重复第二步和第三步，直到所有节点都被处理过。

以下是伪代码和部分C++代码实现：

#include <vector>
using namespace std;

class Graph {
private:
    vector<int> indegrees; // 存储每个节点的入度
    vector<vector<int>> adjList; // 邻接表

public:
    void addEdge(int src, int dest) {
        adjList[src].push_back(dest);
        indegrees[dest]++;
    }

    vector<int> topologicalSort() {
        vector<int> result;
        queue<int> q;

        // 初始化：入度为0的节点入队
        for (int i = 0; i < indegrees.size(); ++i) {
            if (indegrees[i] == 0)
                q.push(i);
        }

        while (!q.empty()) {
            int node = q.front();
            q.pop();

            result.push_back(node); // 将节点添加到结果列表
            for (int neighbor : adjList[node]) {
                indegrees[neighbor]--;
                if (indegrees[neighbor] == 0)
                    q.push(neighbor);
            }
        }

        return result.size() == indegrees.size() ? result : vector<int>(); // 如果所有节点都已处理，返回结果；否则表示有循环
    }
};

// 使用示例
Graph g;
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 3);

vector<int> sortedOrder = g.topologicalSort();