9.图--拓补排序

1.概念

• 无环图：

• 活动
• 

2.  拓补序列：

3.拓补排序：对有向图构造拓补序列的过程

1.1.例子

比如有下表，要学习“汇编语言”就需要先学习C1和C13课程。

要将表画为AOV网图：

拓补序列始终是向后指的，不能向前指（向前指是错误的）

对AOV网图进行拓补排序的方法和步骤如下：

数据结构表示：用邻接表表示AOV网图

 其中C1和C12入度都为0

算法函数代码

//边节点声明
#define MAXVEX 9
typedef struct EdgeNode
{
    int adjvex;//顶点数据的值
    struct EdgeNode* next;
};

//顶点表节点声明
typedef struct VertexNode
{
    int in;
    int data;
    EdgeNode* firstnode;
}VertexNode, AdjList[MAXVEX];

typedef struct
{
    AdjList adjList;
    int numVertexes, numEdges;
}grapphAdjList, *GraphAdjList;

//拓补排序算法
//如果GL无回路，则输出拓补排序序列并返回true，否则返回false
bool TopologicalSort(GraphAdjList GL)
{
    int top = 0;//用于栈指针下标索引
    int gettop;
    int *stack;
    int k;      //用于提取数值
    EdgeNode* e;
    int count = 0;//用于判断是否存在环
    stack = (int*)malloc(GL->numVertexes * sizeof(int));//用堆栈的方式放入入度为0的顶点

    for (int i=0; i < GL->numVertexes; i++)
    {
        if (GL->adjList[i].in == 0)//如果入度为0
        {
            stack[++top] = i; //将入度为0的顶点下标入栈，stack数组用于记录下标
        }
    }

    while (top != 0)
    {
        gettop = stack[top--];
        printf("%d ->", GL->adjList[gettop].data);
        count++;

        for (e = GL->adjList[gettop].firstnode; e; e = e->next)
        {
            k = e->adjvex;
            //注意：下面的语句是分析整个程序的要点
            //将k号顶点邻接表的入度减1，因为他的前驱已经消除
            //接着判断减1后，入度是否为0，如果为0，则入栈
            if (!(--GL->adjList[k].in))
            {
                stack[top++] = k;
            }

        }
    }
    if (count < GL->numVertexes)
    {
        return false;
    }
    else
        return true;

}