²      问题描述

扩展拓扑排序算法，进行课程学习计划的辅助制定。一个学生在一个学期可以同时学习多门课程，同一学期的各门课程之间必须不存在次序关系，制定课程计划使学生可以在最短时间内学完所有课程。

源程序：

#include<stdio.h>
#include <stdio.h>
#include <stdlib.h>
#define MaxVertexNum 100
typedef int VertexType;
typedef struct node{
    int adjvex;
    struct node *next;
}EdgeNode;
typedef struct vnode{
    VertexType vertex;
    char name[20];
    EdgeNode *firstedge;
}VertexNode;
typedef VertexNode AdjList[MaxVertexNum];
typedef enum{
   FALSE,TRUE
}Boolean;
typedef struct{
    AdjList adjlist;
    int n,e;
}ALGraph;
typedef int DataType;
typedef struct stacknode{
    DataType data;
    struct  stacknode  *next;
}StackNode;
typedef struct{
    StackNode *top;
}LinkStack;
void InitStack(LinkStack *S)
{
 S->top=NULL;
}
int StackEmpty(LinkStack *S)
{
 return S->top==NULL;
}
void Push(LinkStack *S,DataType x)
{
 StackNode *p;
 p=(StackNode *)malloc(sizeof(StackNode));
 p->data=x;
 p->next=S->top;
 S->top=p;
}
DataType Pop(LinkStack *S)
{
 DataType x;
 StackNode *p=S->top;
 if (StackEmpty(S))
    printf("Stack underflow!");
 x=p->data;
 S->top=p->next;
 free(p);
 return x;
}
void CreateALGraph(ALGraph *G)
{int i,j,k;
 EdgeNode *s;
 printf("\nEnter n & e:\n");
 scanf("%d%d",&G->n,&G->e);
 printf("Enter the courses' number & name:\n");
 for (i=0;i<G->n;i++)
   {
    scanf("%d%s",&G->adjlist[i].vertex,G->adjlist[i].name);
    G->adjlist[i].firstedge=NULL;
   }
 printf("Enter edge:\n");
 for (k=0;k<G->e;k++)
   {
    scanf("%d%d",&i,&j);
    s=(EdgeNode *)malloc(sizeof(EdgeNode));
    s->adjvex=j;
    s->next=G->adjlist[i].firstedge;
    G->adjlist[i].firstedge=s;
   }
}
void NonPreFirstTopSort(ALGraph *G)
{
 int indegree[MaxVertexNum],i,j,count=0,k=1,flag,t;
 LinkStack S;
 EdgeNode *p;
 Boolean B[MaxVertexNum];
 for(i=0;i<G->n;i++)
   {
    indegree[i]=0;
    B[i]=FALSE;
   }
 for(i=0;i<G->n;i++)
    for(p=G->adjlist[i].firstedge;p;p=p->next)
       indegree[p->adjvex]++;
 InitStack(&S);
 while(count<G->n)
  {
   printf("The %d term:",k++);
   for(i=0;i<G->n;i++)
      if(indegree[i]==0 && B[i]==FALSE)
        {
  printf("(%d %s)   ",G->adjlist[i].vertex,G->adjlist[i].name);
  B[i]=TRUE;
         count++;
  Push(&S,i);
        }
   printf("\n");
   while(!StackEmpty(&S))
    {
     i=Pop(&S);
     for(p=G->adjlist[i].firstedge;p;p=p->next)
      {
       j=p->adjvex;
       indegree[j]--;
      }
    }
   flag=0;
   for(t=0;t<G->n;t++)
      for(p=G->adjlist[t].firstedge;p;p=p->next)
  if(indegree[p->adjvex]==0 && B[p->adjvex]==FALSE)
          {
           flag=1;
           break;
          }
   if(flag==0 && count<G->n)
    {
     printf("\nThe Graph is not a DAG .\n");
     return;
    }
 }
}
void main()
{
 ALGraph *G;
 void CreateALGraph(ALGraph *G);
 void NonPreFirstTopSort(ALGraph *G);
 CreateALGraph(G);
 NonPreFirstTopSort(G);
}