我这里的拓扑排序为啥没有输出来？

Question

我这里的拓扑排序为啥没有输出来？

完整代码：
KeyPath.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;
    int weight;
}ArcNode;

typedef struct
{
    ArcNode* firstarc;
    int count;
}VNode;

typedef struct
{
    VNode adjlist[MAXV];
    int n, e;
}AdjGraph;

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

void KeyPath(AdjGraph* G);

KeyPath.cpp:

#include"KeyPath.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 = j;
                p->weight = A[i][j];
                p->nextarc = G->adjlist[i].firstarc;
                G->adjlist[i].firstarc = p;
            }
        }
    }
}

void TopSort(AdjGraph* G, int topsort[])
{
    int i = 0;
    ArcNode* p = NULL;
    int St[MAXV];
    int top = -1;
    int k = -1;
    for (i = 0; i < G->n; i++)
    {
        G->adjlist[i].count = 0;
    }
    for (i = 0; i < G->n; i++)
    {
        p = G->adjlist[i].firstarc;
        while (p != NULL)
        {
            G->adjlist[p->adjvex].count++;
            p = p->nextarc;
        }
    }
    for (i = 0; i < G->n; i++)
    {
        if (G->adjlist[i].count == 0)
        {
            St[++top] = i;
        }
    }
    while (top > -1)
    {
        i = St[top--];
        topsort[++k] = 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;
        }
    }
    if (k < G->n)
        return;
    else
    {
        printf("拓扑序列为：\n");
        for (i = 0; i < G->n; i++)
            printf("%c ", (char)(topsort[i] + 'A'));
        printf("\n");
    }
}

void KeyPath(AdjGraph* G)
{
    int ee[MAXV] = { 0 };
    int el[MAXV];
    int ve;
    int vl;
    int topsort[MAXV];
    TopSort(G, topsort);
    int lnode = topsort[0];
    int enode = topsort[G->n - 1];
    int i = 0;
    ArcNode* p = NULL;
    for (i = 0; i < G->n; i++)
    {
        p = G->adjlist[i].firstarc;
        while (p != NULL)
        {
            if (p->weight + ee[i] > ee[p->adjvex])
            {
                ee[p->adjvex] = p->weight + ee[i];
            }
            p = p->nextarc;
        }
    }
    for (i = 0; i < G->n; i++)
    {
        el[i] = ee[enode];
    }
    for (i = G->n - 2; i >= 0; i--)
    {
        p = G->adjlist[i].firstarc;
        while (p != NULL)
        {
            //if (ee[i] - p->weight < el[i])
            if (el[i] - p->weight < el[i])
            {
                el[i] = ee[i] - p->weight;
            }
            p = p->nextarc;
        }
    }
    for (i = 0; i < G->n; i++)
    {
        p = G->adjlist[i].firstarc;
        while (p != NULL)
        {
            ve = ee[i];
            vl = el[p->adjvex] - p->weight;
            if (ve == vl)
            {
                printf("%3d%3d%3d\n", i, p->adjvex, p->weight);
            }
            p = p->nextarc;
        }
    }
}

test.cpp:

#include"KeyPath.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);
    KeyPath(G);
    return 0;
}

Answer 1

首先，我注意到你的TopSort函数没有返回值，但是在一些情况下你试图返回（return;），这可能会引起编译器警告。此外，我建议在main函数中添加对图是否为空的检查，确保图已经被正确创建。

然后，有一个关键的问题在于拓扑排序函数TopSort()。在该函数中，如果顶点数量k小于图的顶点数量G->n，函数就会直接返回，这意味着如果图中存在环，函数将不会进行任何输出。

在你的代码中，似乎在所有情况下，TopSort()函数都没有对外输出结果。这可能是因为你的图G存在环。由于拓扑排序只能在有向无环图（DAG）上进行，因此，如果你的图存在环，拓扑排序将失败。

为了解决这个问题，你需要检查输入的图是否存在环。你可以使用深度优先搜索（DFS）或并查集等方法来检测图中是否存在环。如果存在环，你需要修改输入的图，使其成为一个DAG，然后再进行拓扑排序。

最后，在KeyPath()函数中，我注意到这一行可能有误：

el[i] = ee[i] - p->weight;

应改为：

el[p->adjvex] = el[i] - p->weight;

这是因为你要更新目标顶点p->adjvex的最晚开始时间，而非源顶点i。