拓扑序列一定等于有向无环图的点数吗

不一定。拓扑序列是指一个有向无环图的所有节点按照拓扑排序的顺序排列成的序列，而有向无环图的节点数可能大于或小于拓扑序列的长度。如果有向无环图中存在孤立节点（即没有入度也没有出度的节点），则这些节点不会出现在任何一个拓扑序列中，因此拓扑序列的长度可能小于节点数。反之，如果有向无环图中存在多个入度为0的节点，则它们在拓扑排序中可能具有不同的顺序，从而使得拓扑序列的长度大于节点数。

相关问题

判断上图是否含有环，若没有则输出其拓扑序列。（C语言）

这是一个经典的拓扑排序问题。可以使用邻接表来表示图，然后使用队列实现拓扑排序。

以下是一个示例代码实现：

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

#define MAX_VERTEX_NUM 100 // 最大顶点数

typedef struct ArcNode {
    int adjvex; // 邻接顶点
    struct ArcNode* nextarc; // 指向下一个邻接点的指针
} ArcNode;

typedef struct VertexNode {
    int data; // 顶点数据
    ArcNode* firstarc; // 指向第一条依附该顶点的弧的指针
} VertexNode;

typedef struct {
    VertexNode vertex[MAX_VERTEX_NUM]; // 顶点数组
    int vexnum, arcnum; // 顶点数和弧数
} Graph;

// 初始化图
void initGraph(Graph* G, int n) {
    G->vexnum = n;
    G->arcnum = 0;
    for (int i = 0; i < n; i++) {
        G->vertex[i].data = i;
        G->vertex[i].firstarc = NULL;
    }
}

// 添加一条边
void addEdge(Graph* G, int v, int w) {
    ArcNode* arc = (ArcNode*)malloc(sizeof(ArcNode));
    arc->adjvex = w;
    arc->nextarc = G->vertex[v].firstarc;
    G->vertex[v].firstarc = arc;
    G->arcnum++;
}

// 拓扑排序
void topologicalSort(Graph* G) {
    // 入度数组
    int* indegree = (int*)calloc(G->vexnum, sizeof(int));
    for (int i = 0; i < G->vexnum; i++) {
        for (ArcNode* arc = G->vertex[i].firstarc; arc != NULL; arc = arc->nextarc) {
            indegree[arc->adjvex]++;
        }
    }

    // 将入度为0的顶点加入队列
    int* queue = (int*)malloc(G->vexnum * sizeof(int));
    int front = 0, rear = 0;
    for (int i = 0; i < G->vexnum; i++) {
        if (indegree[i] == 0) {
            queue[rear++] = i;
        }
    }

    // 拓扑排序
    while (front != rear) {
        int v = queue[front++];
        printf("%d ", v);
        for (ArcNode* arc = G->vertex[v].firstarc; arc != NULL; arc = arc->nextarc) {
            indegree[arc->adjvex]--;
            if (indegree[arc->adjvex] == 0) {
                queue[rear++] = arc->adjvex;
            }
        }
    }

    printf("\n");

    free(indegree);
    free(queue);
}

int main() {
    Graph G;
    initGraph(&G, 6);
    addEdge(&G, 0, 1);
    addEdge(&G, 0, 2);
    addEdge(&G, 1, 3);
    addEdge(&G, 2, 3);
    addEdge(&G, 2, 4);
    addEdge(&G, 3, 5);
    addEdge(&G, 4, 5);

    topologicalSort(&G);

    return 0;
}

以上代码实现的拓扑排序算法的时间复杂度为 $O(|V|+|E|)$，其中 $|V|$ 表示顶点数，$|E|$ 表示边数。

使用c对有向无环图，按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。由此所得顶点的线性序列称之为拓扑有序序列。 输入有向图的相关信息，若图中无环，输出其拓扑有序序列，否则输出“此有向图不是有向无环图”。 因拓扑有序序列不唯一，故要求如下： （1）使用邻接表存储图。邻接表的每个链表中，要求按顶点的序号从大到小排列； （2）使用栈辅助操作。初始时，入度为0的顶点入栈时，也按顶点的序号从大到小的顺序入栈。 输入说明： 输入有向图的顶点数、边数、各顶点的值，各边的信息。 输出说明： 若有向图中无环，输出其拓扑有序序列，否则输出“此有向图不是有向无环图”。 拓扑有序序列的每个顶点数据后有一个空格。 输入样例： 6 8 1 2 3 4 5 6 1 2 1 3 1 4 3 2 3 5 4 5 6 4 6 5 输出样例： 1 3 2 6 4 5

以下是使用C语言实现的拓扑排序代码，使用邻接表存储图，使用栈辅助操作：

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

#define MAXVEX 100 // 最大顶点数

// 边表结点
typedef struct EdgeNode {
    int adjvex;             // 邻接点域，存储该顶点对应的下标
    struct EdgeNode *next;  // 链域，指向下一个邻接点
} EdgeNode;

// 顶点表结点
typedef struct VertexNode {
    int data;            // 顶点域，存储顶点信息
    EdgeNode *firstedge; // 边表头指针
} VertexNode, AdjList[MAXVEX];

// 图结构
typedef struct {
    AdjList adjList; // 邻接表
    int numVertexes; // 图中当前的顶点数
    int numEdges;    // 图中当前的边数
} GraphAdjList;

// 入度数组
int indegree[MAXVEX];

// 拓扑排序
int TopologicalSort(GraphAdjList *G) {
    int i, k, count = 0;
    int top = -1;
    EdgeNode *e;

    // 初始化入度数组
    for (i = 0; i < G->numVertexes; i++) {
        indegree[i] = 0;
    }

    // 计算所有顶点的入度
    for (i = 0; i < G->numVertexes; i++) {
        e = G->adjList[i].firstedge;
        while (e != NULL) {
            indegree[e->adjvex]++;
            e = e->next;
        }
    }

    // 将所有入度为0的顶点入栈
    for (i = G->numVertexes - 1; i >= 0; i--) {
        if (indegree[i] == 0) {
            top++;
            stack[top] = i;
        }
    }

    // 拓扑排序
    while (top != -1) {
        k = stack[top];
        top--;
        printf("%d ", G->adjList[k].data);
        count++;
        e = G->adjList[k].firstedge;
        while (e != NULL) {
            indegree[e->adjvex]--;
            if (indegree[e->adjvex] == 0) {
                top++;
                stack[top] = e->adjvex;
            }
            e = e->next;
        }
    }

    // 如果排序后顶点数小于总数，则说明存在环
    if (count < G->numVertexes) {
        return -1;
    }

    return 0;
}

int main() {
    int i, j, k;
    GraphAdjList G;
    EdgeNode *e;

    // 输入顶点数和边数
    scanf("%d %d", &G.numVertexes, &G.numEdges);

    // 输入顶点信息
    for (i = 0; i < G.numVertexes; i++) {
        scanf("%d", &G.adjList[i].data);
        G.adjList[i].firstedge = NULL;
    }

    // 输入边信息，构建邻接表
    for (k = 0; k < G.numEdges; k++) {
        scanf("%d %d", &i, &j);

        // 新建一个边表结点
        e = (EdgeNode *)malloc(sizeof(EdgeNode));
        e->adjvex = j;

        // 将e插入到顶点i的边表头部
        e->next = G.adjList[i].firstedge;
        G.adjList[i].firstedge = e;
    }

    // 拓扑排序
    if (TopologicalSort(&G) == -1) {
        printf("此有向图不是有向无环图\n");
    }

    return 0;
}