有向图n个点e条边拓扑

拓扑排序是一种针对有向无环图（DAG）的排序算法，它可以将有向图中的节点排序，使得每个节点的入度都比它小。如果给定的有向图有环，则该算法无法进行拓扑排序。

基本思路是通过不断地移除图中入度为0的节点，并删除与之相邻的有向边，直到所有的节点都被移除为止。如果存在入度不为0的节点，则说明图中存在环。

拓扑排序的时间复杂度为O(n+e)，其中n为节点数，e为边数。

相关问题

有向无环图 拓扑排序 c++ 模板

以下是C++实现有向无环图的拓扑排序的模板：

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int h[N], e[N], ne[N], idx;
int d[N]; // 入度
int q[N]; // 存储拓扑序
int n, m;

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

bool topsort() {
    int hh = 0, tt = -1;

    for (int i = 1; i <= n; i ++ )
        if (!d[i])
            q[ ++ tt] = i;

    while (hh <= tt) {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (-- d[j] == 0)
                q[ ++ tt] = j;
        }
    }

    return tt == n - 1;
}

int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);

    while (m -- ) {
        int a, b;
        cin >> a >> b;
        add(a, b);
        d[b] ++ ;
    }

    if (topsort())
        for (int i = 0; i < n; i ++ ) cout << q[i] << ' ';
    else puts("-1");

    return 0;
}

其中，`add`函数用于建图，`topsort`函数用于进行拓扑排序。时间复杂度为 O(n + m)。

数据结构与算法：用C语言实现基于邻接表存储有向图的拓扑排序

拓扑排序是对有向无环图(DAG)的所有节点进行排序，使得对于每一条有向边(u,v)，在排序后的节点序列中，节点u都排在节点v的前面。下面是用C语言实现基于邻接表存储有向图的拓扑排序的代码：

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

#define MAXV 1000  // 最大顶点数

typedef struct node{
    int v;  // 存储的顶点
    struct node *next;  // 指向下一个节点的指针
}node;

node *G[MAXV];  // 存储图的邻接表
int inDegree[MAXV];  // 存储各个顶点的入度
int V, E;  // 顶点数和边数

// 向邻接表中添加一条边
void addEdge(int u, int v){
    node *newNode = (node*)malloc(sizeof(node));
    newNode->v = v;
    newNode->next = G[u];
    G[u] = newNode;
}

// 用拓扑排序对DAG进行排序
void topologicalSort(){
    int i, j;
    int queue[MAXV], front = 0, rear = -1;  // 队列实现
    int cnt = 0;  // 记录已经输出的顶点数

    // 将入度为0的顶点入队
    for(i = 0; i < V; i++){
        if(inDegree[i] == 0){
            queue[++rear] = i;
        }
    }

    while(front <= rear){
        int u = queue[front++];  // 取出队首元素
        printf("%d ", u);
        cnt++;

        // 将所有u指向的顶点的入度减1
        for(node *p = G[u]; p != NULL; p = p->next){
            int v = p->v;
            inDegree[v]--;
            // 如果v的入度为0，将v入队
            if(inDegree[v] == 0){
                queue[++rear] = v;
            }
        }
    }

    // 如果输出的顶点数小于V，说明图中有环
    if(cnt < V){
        printf("Error: Graph contains cycle!\n");
    }
}

int main(){
    int i, u, v;

    scanf("%d%d", &V, &E);  // 输入顶点数和边数

    // 初始化邻接表和入度数组
    for(i = 0; i < V; i++){
        G[i] = NULL;
        inDegree[i] = 0;
    }

    // 读入边，建立邻接表和入度数组
    for(i = 0; i < E; i++){
        scanf("%d%d", &u, &v);
        addEdge(u, v);
        inDegree[v]++;
    }

    topologicalSort();  // 拓扑排序

    return 0;
}

在这个程序中，我们使用了邻接表存储图，并且记录了每个顶点的入度。在拓扑排序时，我们使用了队列实现。我们先将入度为0的顶点入队，然后不断从队列中取出元素，输出该元素，并将所有该元素指向的顶点的入度减1。如果减1后该顶点的入度变为0，就将该顶点入队。当队列为空时，如果输出的顶点数小于总顶点数，说明图中存在环。