已知图的邻接表如下所示(“/”表示空指针)，现进行拓扑排序，采用栈存放零入度点，正确拓扑序列是V1V3V5V4V2为什么不是V1V3V5V2V4？ 邻接表如下： 0 V1→2→1→3 / 1 V2 / 2 V3→3→4 / 3 V4 / 4 V5→1→3 /

在进行拓扑排序时，首先需要找到入度为 0 的点，然后将其加入拓扑序列中，并将其指向的点的入度减 1。然后继续寻找入度为 0 的点，直到所有点都被加入拓扑序列中。

根据所给的邻接表，可以计算每个点的入度：

- V1 的入度为 0
- V2 的入度为 1（来自 V1）
- V3 的入度为 1（来自 V1）
- V4 的入度为 2（来自 V1 和 V3）
- V5 的入度为 0

因此，首先将入度为 0 的点加入拓扑序列中，即 V1 和 V5。然后，将 V1 和 V5 指向的点的入度减 1，得到以下邻接表：

0 V1→2→1→3 /
1 V2 /
2 V3→3→4 /
3 V4 /
4 V5→1→3 /

接下来，入度为 0 的点是 V3 和 V2。因为 V3 的入度为 1，所以需要先将其加入拓扑序列中，并将其指向的点的入度减 1。得到以下邻接表：

0 V1→2→1→3 /
1 V2 /
2 V3→4 /
3 V4 /
4 V5→1→3 /

现在入度为 0 的点是 V2 和 V5。因为 V2 的入度为 1，所以需要先将其加入拓扑序列中，并将其指向的点的入度减 1。得到以下邻接表：

0 V1→2→1→3 /
1 /
2 V3→4 /
3 V4 /
4 V5→1→3 /

最后，入度为 0 的点是 V1。将其加入拓扑序列中，并将其指向的点的入度减 1。得到以下邻接表：

0 /
1 /
2 V3→4 /
3 V4 /
4 V5→1→3 /

此时所有点都已经加入拓扑序列中，且没有出现环，因此拓扑排序的结果为 V1V3V5V4V2，而不是 V1V3V5V2V4。

相关问题

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

好的，以下是实现的步骤：

1. 首先定义有向图的邻接表结构体，包括每个节点的入度、出度及指向下一个节点的指针数组。

typedef struct node{
    int val; //顶点值
    int in_degree; //入度
    int out_degree; //出度
    struct node *next; //指向下一个节点的指针数组
}Node;

typedef struct graph{
    int v_num; //节点数目
    Node **adj_list; //邻接表
}Graph;

2. 定义栈结构体和相关操作函数，用于进行拓扑排序时的存储和输出。

typedef struct stack{
    int top;
    int *data;
}Stack;

Stack* create_stack(int size){
    Stack *s = (Stack*)malloc(sizeof(Stack));
    s->top = -1;
    s->data = (int*)malloc(sizeof(int)*size);
    return s;
}

void push(Stack *s, int val){
    s->data[++s->top] = val;
}

int pop(Stack *s){
    return s->data[s->top--];
}

int is_empty(Stack *s){
    return s->top == -1;
}

3. 实现有向图的创建函数，根据输入的节点数目和每个节点的出度建立邻接表。

Graph* create_graph(int v_num){
    Graph *g = (Graph*)malloc(sizeof(Graph));
    g->v_num = v_num;
    g->adj_list = (Node**)malloc(sizeof(Node*)*v_num);
    for(int i=0; i<v_num; i++){
        g->adj_list[i] = (Node*)malloc(sizeof(Node));
        g->adj_list[i]->val = i;
        g->adj_list[i]->in_degree = 0;
        g->adj_list[i]->out_degree = 0;
        g->adj_list[i]->next = NULL;
    }

    for(int i=0; i<v_num; i++){
        int out;
        printf("Enter out degree of vertex %d: ", i);
        scanf("%d", &out);
        for(int j=0; j<out; j++){
            int to;
            printf("Enter vertex pointed by vertex %d: ", i);
            scanf("%d", &to);

            Node* new_node = (Node*)malloc(sizeof(Node));
            new_node->val = to;
            new_node->in_degree++;
            new_node->next = g->adj_list[i]->next;
            g->adj_list[i]->next = new_node;
            g->adj_list[i]->out_degree++;
        }
    }

    return g;
}

4. 实现拓扑排序函数，依次遍历邻接表中的每个节点，将入度为0的节点入栈，然后将其指向的节点的入度减1，若其入度变为0，则入栈。直到栈为空。

void topological_sort(Graph *g){
    Stack *s = create_stack(g->v_num);
    for(int i=0; i<g->v_num; i++){
        if(g->adj_list[i]->in_degree == 0){
            push(s, i);
        }
    }

    while(!is_empty(s)){
        int node = pop(s);
        printf("%d ", node);
        Node *p = g->adj_list[node]->next;
        while(p){
            if(--g->adj_list[p->val]->in_degree == 0){
                push(s, p->val);
            }
            p = p->next;
        }
    }
}

5. 在主函数中调用以上函数进行测试。

int main(){
    int v_num;
    printf("Enter number of vertices in graph: ");
    scanf("%d", &v_num);

    Graph *g = create_graph(v_num);
    printf("Topological order of graph: ");
    topological_sort(g);

    return 0;
}

完整代码如下：

生成一个带“入度”域的图，邻接表存储。写一个拓扑排序算法

以下是生成带“入度”域的图并实现拓扑排序的C语言代码：

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

#define MAX_VERTEX_NUM 20   // 最大顶点数

// 定义邻接表节点结构体
typedef struct ArcNode {
    int adjvex;             // 该边所指向的顶点的位置
    struct ArcNode *next;   // 指向下一条边的指针
} ArcNode;

// 定义顶点信息结构体
typedef struct {
    char data;              // 顶点数据
    int indegree;           // 顶点入度
    ArcNode *firstarc;      // 指向第一个依附该顶点的边的指针
} VNode;

// 定义邻接表结构体
typedef struct {
    VNode vertices[MAX_VERTEX_NUM];    // 存放顶点信息的数组
    int vexnum, arcnum;                 // 顶点数和边数
} ALGraph;

// 初始化邻接表
void InitALGraph(ALGraph *G) {
    int i;
    G->vexnum = 0;
    G->arcnum = 0;
    for (i = 0; i < MAX_VERTEX_NUM; i++) {
        G->vertices[i].firstarc = NULL;
        G->vertices[i].indegree = 0;
    }
}

// 添加边
void AddArc(ALGraph *G, int start, int end) {
    ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
    p->adjvex = end;
    p->next = G->vertices[start].firstarc;
    G->vertices[start].firstarc = p;
    G->vertices[end].indegree++;    // 相应顶点入度加1
    G->arcnum++;
}

// 拓扑排序
int TopoSort(ALGraph *G) {
    int i, j, k, count = 0;
    int result[MAX_VERTEX_NUM];     // 存放拓扑排序结果的数组
    ArcNode *p;
    for (i = 0; i < G->vexnum; i++) {   // 将所有入度为0的顶点入队
        if (G->vertices[i].indegree == 0) {
            result[count++] = i;
        }
    }
    for (i = 0; i < count; i++) {   // 依次输出队首顶点，并将该顶点的所有邻接点的入度减1
        j = result[i];
        printf("%c ", G->vertices[j].data);
        for (p = G->vertices[j].firstarc; p; p = p->next) {
            k = p->adjvex;
            if (--G->vertices[k].indegree == 0) {
                result[count++] = k;
            }
        }
    }
    if (count < G->vexnum) {    // 如果输出的顶点数少于总顶点数，则说明存在环，拓扑排序失败
        return 0;
    } else {
        return 1;
    }
}

// 测试代码
int main() {
    ALGraph G;
    InitALGraph(&G);
    G.vexnum = 6;
    G.arcnum = 8;
    G.vertices[0].data = 'A';   // 添加顶点数据和入度
    G.vertices[1].data = 'B';
    G.vertices[2].data = 'C';
    G.vertices[3].data = 'D';
    G.vertices[4].data = 'E';
    G.vertices[5].data = 'F';
    AddArc(&G, 0, 1);   // 添加边
    AddArc(&G, 0, 3);
    AddArc(&G, 1, 2);
    AddArc(&G, 1, 3);
    AddArc(&G, 3, 2);
    AddArc(&G, 3, 4);
    AddArc(&G, 2, 5);
    AddArc(&G, 4, 5);
    if (TopoSort(&G)) { // 执行拓扑排序
        printf("\n拓扑排序成功\n");
    } else {
        printf("\n拓扑排序失败，存在环\n");
    }
    return 0;
}

在上述代码中，我们定义了一个邻接表结构体`ALGraph`，其中`vertices`数组存放顶点信息，`vexnum`表示顶点数，`arcnum`表示边数。我们用`AddArc`函数向邻接表中添加边，用`TopoSort`函数进行拓扑排序。在测试代码中，我们添加了一些边，并且执行了拓扑排序。如果拓扑排序成功，则输出拓扑排序结果，否则说明存在环，拓扑排序失败。