这个图按道理来讲拓扑排序的结果不应该是0，1，2,3,4,5,6,7,8吗（如图二），为什么我的代码输出来的却是逆着的，并且还没有0,感觉代码也都挺完美的

这个图按道理来讲拓扑排序的结果不应该是0，1，2,3,4,5,6,7,8吗（如图二），为什么我的代码输出来的却是逆着的，并且还没有0,感觉代码也都挺完美的

img

img


完整代码:
AdjGraph.h:

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>

#define MAXV 20
#define INF 32767
typedef struct ANode
{
    int adjvex;
    struct ANode* nextarc;
}ArcNode;
typedef struct
{
    int count;
    ArcNode* firstarc;
}VNode;
typedef struct
{
    VNode adjlist[MAXV];
    int n;
    int e;
}AdjGraph;

void CreateGraph(AdjGraph*& G, int A[][MAXV], int n, int e);

void TopSort(AdjGraph* G);

AdjGraph.cpp:

#include"AdjGraph.h"
void CreateGraph(AdjGraph*& G, int A[][MAXV], int n, int e)
{
    G = (AdjGraph*)malloc(sizeof(AdjGraph));
    G->n = n;
    G->e = e;
    int i = 0;
    int j = 0;
    ArcNode* p = NULL;
    for (i = 0; i < G->n; i++)
    {
        G->adjlist[i].firstarc = NULL;
        for (j = 0; j < G->n; j++)
        {
            if (A[i][j] != 0 && A[i][j] != INF)
            {
                p = (ArcNode*)malloc(sizeof(ArcNode));
                p->adjvex = i;
                p->nextarc = G->adjlist[i].firstarc;
                G->adjlist[i].firstarc = p;
            }
        }
    }
}

void TopSort(AdjGraph* G)
{
    int i = 0;
    ArcNode* p = NULL;
    int st[MAXV], top = -1;
    for (i = 0; i < G->n; i++)//初始化count
    {
        G->adjlist[i].count = 0;
    }
    for (i = 0; i < G->n; i++)//计算每个结点的入度
    {
        p = G->adjlist->firstarc;
        while (p != NULL)
        {
            G->adjlist[p->adjvex].count++;
            p = p->nextarc;
        }
    }
    for (i = 0; i < G->n; i++)//让每个度为0的入栈
    {
        if (G->adjlist[i].count == 0)
        {
            st[++top] = i;
        }
    }
    while (top != -1)
    {
        i = st[top--];
        printf("%d ", i);
        p = G->adjlist[i].firstarc;
        while (p != NULL)
        {
            G->adjlist[p->adjvex].count--;
            if (G->adjlist[p->adjvex].count == 0)
            {
                st[++top] = p->adjvex;
            }
            p = p->nextarc;
        }
    }
}

test.cpp:

#include"AdjGraph.h"
int main()
{
    int A[MAXV][MAXV] = { 
        {0, 6, 4, 5, INF, INF, INF, INF, INF},
        {INF, 0, INF, INF, 1, INF, INF, INF, INF},
        {INF, INF, 0, INF, 1, INF, INF, INF, INF},
        {INF, INF, INF, 0, INF, INF, INF, 2, INF},
        {INF, INF, INF, INF, 0, 9, 7, INF, INF},
        {INF, INF, INF, INF, INF, 0, INF, INF, 2},
        {INF, INF, INF, INF, INF, INF, 0, INF, 4},
        {INF, INF, INF, INF, INF, INF, INF, 0, 4},
        {INF, INF, INF, INF, INF, INF, INF, INF, 0} };
    int n = 9, e = 11;
    AdjGraph* G;
    CreateGraph(G, A, n, e);
    TopSort(G);
    return 0;
}