图——拓扑排序

拓扑排序

AOV网，描述了一种有实际意义的过程，所以结点之间有了先后顺序，其次是结点之间是没有环的。
如何导出正确的结点之间的顺序，就需要拓扑排序。三个步骤:

tuopu

用邻接表来存储图，且修改顶点结构体为

1
2
3
4
5
6
typedef struct
{
	int data;
	int count; //指示当前结点的入度
	ArcNode* first;
}VNode;

拓扑排序的代码实现：

int TopSort(AGraph *G)
{
    int i ,j ,n=0; //n统计当前已经输出的顶点个数
    int stack[maxSize],top=-1; //定义一个栈，保存所有入度为0的顶点
    ArcNode* p; //遍历

    for(i=0;i<G->n;++i)
        if(G->adjList[i].count==0)
            stack[++top]=i; //将入度为0的压栈

    while(top!=-1)//若栈不为0，
    {
        i=stack[top--]; //取出顶点，等效于将这个顶点删除，
        ++n;  //记录取出的点的个数，
        std::cout<<i<<" ";  //输出这个顶点

        p=G->adjList[i].first; //遍历刚才出栈顶点的所有边，
        while(p!=NULL)
        {
            j=p->adjV; //通过这些边找到其相邻顶点，
            --(G->adjList[j].count); //修改其count
            if(G->adjList[j].count==0) //然后将count为0的点入栈，以待输出
                stack[++top]=j;
            p=p->next;
        }

    }
    if(n==G->n) //输出的顶点个数是否为图中顶点的个数
        return 1;  //相等则拓扑排序完成
    else
        return 0;

}```



**逆拓扑排序**    


<img src="https://github.com/fanandli/picblog/blob/master/nituopupaixu.png?raw=true" width = "600" height = "350" alt="tuopu1" align=center />



如何用深度优先遍历实现逆拓扑排序
深度优先遍历：

<img src="https://github.com/fanandli/picblog/blob/master/shenduyouxianbianli.png?raw=true" width = "600" height = "350" alt="tuopu2" align=center />


以此实现逆拓扑排序：
<img src="https://github.com/fanandli/picblog/blob/master/tuopupaixushixian.png?raw=true" width = "600" height = "350" alt="tuopu3" align=center />