实验题目: 拓扑排序

实验题目: 拓扑排序。任意给定一个有向图，设计一个算法，对它进行拓扑排序。拓扑排序算法思想：a.在有向图中任选一个没有前趋的顶点输出；b.从图中删除该顶点和所有以它为尾的弧；c.重复上述a、b，直到全部顶点都已输出，此时，顶点输出序列即为一个拓朴有序序列；或者直到图中没有无前趋的顶点为止，此情形表明有向图中存在环。

实验说明：拓扑排序算法伪代码如下：

1. 栈S初始化；累加器count初始化；

2. 扫描顶点表，将没有前驱（即入度为0）的顶点压栈；

3. 当栈S非空时循环

    3.1 v_j=退出栈顶元素；输出v_j；累加器加1；

3.2 将顶点v_j的各个邻接点的入度减1；

3.3 将新的入度为0的顶点入栈；

4. if (count<vertexNum) 输出有回路信息；

#include<stdio.h>
#include<stdlib.h>
#define maxv 6//最大顶点个数
#define inf 32767 //考虑若是带权图的其它情况是∞
typedef struct
{
    int no;//顶点的编号
    int num;//顶点的值
}VertexType;//顶点类型


typedef struct
{
    int edges[maxv][maxv];//邻接矩阵数组；
    int n,e;//顶点数。边数
    VertexType verxs[maxv];//顶点信息
}MatGraph;//邻接矩阵类型


typedef struct Anode
{
    int sdjvex;//邻接点的编号
    struct Anode *nextarc;//指向下一条边的指针
}ArcNode;//边结点类型


typedef struct Vnode
{
    VertexType data;//顶点信息
    int count;//在之前的基础上增加了这一项，存放顶点入读
    ArcNode *fistarc;//指向第一个边结点
}VNode;//邻接表的头结点类型；


typedef struct
{
    int  n,e;//定点数，边数
    VNode adjlist[maxv];//头结点数组
}AdjGraph;//邻接表类型


void CreateAdj(AdjGraph *&G,int A[maxv][maxv],int n,int e)//创建图的邻接表
{
    int i,j;//用于循环的临时变量
    ArcNode *p;//边结点类型指针
    G=(AdjGraph *)malloc(sizeof(AdjGraph));//这里默认我在主函数里面仅仅定义了一个结构体指针，
    //                                      没有为结构体分配空间，在这里为它分配空间
    for(i=0;i<n;i++)//n是顶点数，这里是给所有头结点指针域置初值
    {
        G->adjlist[i].fistarc=NULL;
    }
    for(i=0;i<n;i++)//这里不要把邻接矩阵的定义搞错了，n个顶点最多是n*n的矩阵。
    {
        for(j=n-1;j>=0;j--)//这里递减循环，因为采用了头插法
        {
            if(A[i][j]!=0 && A[i][j]!=inf)
            {
                p=(ArcNode*)malloc(sizeof(ArcNode));
                p->sdjvex=j;//i到j有连线，则邻接点为j，即点的编号是j
                p->nextarc=G->adjlist[i].fistarc;//头插法插入结点p；
                G->adjlist[i].fistarc=p;
            }
        }
    }
    G->e=e;
    G->n=n;
}

void DispAdj(AdjGraph *G)//输出邻接表G
{ 
    int i;
    ArcNode *p;
    for(i=0;i<G->n;i++)
    {
        p=G->adjlist[i].fistarc;//p是一个边结点类型的指针，把一个头结点数组元素指向的边结点指针赋给它
        printf("%3d:",i);//输出这是第几个顶点，这个顺序是由你输入的邻接矩阵决定的，算法只是按序扫描
        while(p!=NULL)
        {
            printf("%3d-→",p->sdjvex);
            p=p->nextarc;
        }
        printf("Λ\n");
    }
}

void TopSort(AdjGraph *G)//拓扑排序算法
{
    int i,j;
    int St[maxv],top=-1;//这里St是一个简易的栈
    ArcNode *p;
    for(i=0;i<G->n;i++)
    {
        G->adjlist[i].count=0;//先把所有顶点的入度置为0
    }
    for(i=0;i<G->n;i++)//求所有点的入度
    {
        p=G->adjlist[i].fistarc;//p先指向第一个邻接点
        while(p!=NULL)//进入一个头结点，扫描这个节点下的邻接点
        {
            G->adjlist[p->sdjvex].count++;//一个顶点编号对应一个头结点，用顶点编号来表示某一个头结点是可行的,头结点数组下标即表示这个顶点。
            p=p->nextarc;
        }
    }
    for(i=0;i<G->n;i++)//入度为0的顶点进栈,就是一开始就是入度为零的顶点
    {
        if(G->adjlist[i].count==0)
        {
            top++;
            St[top]=i;
        }
    }
     if(top<=-1)
    {
        printf("该图有回路，没有拓扑序列！！\n");
    }
    int flag=0;////记录输出的顶点个数
    while(top>-1)//若栈不为空则循环，这个用来输出拓扑序列
    {
        
        i=St[top];
        top--;//出栈一个顶点i，这个顶点i就是一开始入度为0的一个顶点；
        printf("%d ",i);//输出该顶点
        
        flag++;//记录输出的顶点个数
        p=G->adjlist[i].fistarc;//然后开始以这个点为基准，把所有出边邻接点的入度减一；
        while(p!=NULL)
        {
            j=p->sdjvex;//把顶点编号赋给j
            G->adjlist[j].count--;//出边邻接点入度减一
            if(G->adjlist[j].count==0)//若入度为0的邻接点，则进栈
            {
                top++;
                St[top]=j;
            }
            p=p->nextarc;
        }
        
    }
    if(flag<G->n)
    {
     printf("该图有回路，没有拓扑序列！！\n");
    }
   printf("\n");
}

int main()
{
    int A[6][6]={{0,1,0,0,0,0},{0,0,1,0,0,0},{0,0,0,1,0,0},{0,0,0,0,0,0},{0,1,0,0,0,1},{0,0,0,1,0,0}};
    AdjGraph *G;
    CreateAdj(G,A,6,6);
     printf("邻接表为：\n");
    DispAdj(G);
    printf("拓扑序列为：\n");
    TopSort(G);
    system("pause");
}