用队列实现图的拓扑排序

#include<stdio.h>
#include<stdlib.h>
#define MAXVEX 100      //最大顶点数
#define MAXSIZE 100 //数组最大长度
typedef char VertexType;     //顶点
typedef int EdgeType;   //权值
#define UNVISITED -1    //标记未访问
#define VISITED 1   //标记未访问
#define OK 1
#define ERROR 0

typedef int Status;
typedef int  QElemtype;
typedef struct
{
    QElemtype data[MAXSIZE];
    int front;
    int rear;
}sqQueue;


//队列的初始化
Status InitQueue(sqQueue * Q)
{
    Q->front=0;
    Q->rear=0;
    return OK;
}



//队列的长度
Status QueueLength(sqQueue Q)
{
    return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}



//入队操作
Status EnQueue(sqQueue * Q, QElemtype e)
{
    if((Q->rear+1)%MAXSIZE==Q->front)
    {
        return ERROR;
    }
    Q->data[Q->rear]=e;
    Q->rear=(Q->rear+1)%MAXSIZE;
    return OK;
}



//出队操作
Status DeQueue(sqQueue * Q,QElemtype * e)
{
    if(Q->front==Q->rear)
    {
        return ERROR;
    }
    *e=Q->data[Q->front];
    Q->front=(Q->front+1)%MAXSIZE;
    return OK;
}




//打印元素
void print(sqQueue * Q)
{
    int length=(Q->rear-Q->front+MAXSIZE)%MAXSIZE;
    for(int i=Q->front;i<length;i++)
    {
        printf("a[%d]=%d ,",i,Q->data[i]);
    }
    printf("\n");
}



//邻接表的存储结构
typedef struct
{
    int from;   //边的始点
    int to; //边的终点
    EdgeType weight;    //权重
}Edge;  //边的结构


typedef struct EdgeNode
{
    int adjvex; //该顶点对应的下标
    EdgeType weight;    //权重
    struct EdgeNode * next;
}EdgeNode;

typedef struct  //顶点结构
{
    VertexType data;
    EdgeNode * firstedge;
}VertexNode,AdjList[MAXVEX];

typedef struct
{
    AdjList adjList;
    int numVertexes;
    int numEdges;
    int Indegree[MAXVEX];
    int Mark[MAXVEX];   //标记是否被访问过
}GraphAdjList;  //图结构


//初始化邻接表
void InitGraphAdjList(GraphAdjList * G,int numVer,int numEd)    //传入顶点数和边数
{
    G->numVertexes=numVer;
    G->numEdges=numEd;
    for(int i=0;i<G->numVertexes;i++)
    {
        G->Mark[i]=UNVISITED;
        G->Indegree[i]=0;
        G->adjList[i].firstedge=NULL;   //将边表置空表
    }
}


//创建一条边(有向图)
void Creat_Edge(GraphAdjList * G,int from,int to,int weight)
{
    EdgeNode * temp= G->adjList[from].firstedge;
    if(temp==NULL)
    {
        EdgeNode * NewEdgeNode=(EdgeNode *)malloc(sizeof(EdgeNode));
        NewEdgeNode->adjvex=to;
        NewEdgeNode->weight=weight;
        NewEdgeNode->next=NULL;
        G->adjList[from].firstedge=NewEdgeNode;
        G->Indegree[to]++;
    }
    else
    {
        while(temp->next!=NULL)
        {
            temp=temp->next;
        }
        EdgeNode * NewEdgeNode=(EdgeNode *)malloc(sizeof(EdgeNode));
        NewEdgeNode->adjvex=to;
        NewEdgeNode->weight=weight;
        NewEdgeNode->next=NULL;
        temp->next=NewEdgeNode;
        G->Indegree[to]++;

    }
}




/*建立图的邻接表结构（有向图）*/
void GreateALGraph(GraphAdjList * G)
{
    int i,j,k,w;
    printf("请输入%d个元素：\n",G->numVertexes);
    for(i=0;i<G->numVertexes;i++)   /*读入顶点信息，建立顶点表*/
    {
        scanf(" %c",&G->adjList[i].data);   /*输入顶点信息*/
        G->adjList[i].firstedge=NULL;   /*将边表置空表*/
    }
    for(k=0;k<G->numEdges;k++)  /*建立边表*/
    {
        printf("输入边(Vi,Vj)上的顶点序号和权重：\n");
        scanf("%d%d%d",&i,&j,&w);   /*输入(Vi,Vj)上的顶点序号*/
        Creat_Edge(G,i,j,w);
    }
}




//返回边表的第一条边
Edge FirstEdge(GraphAdjList * G,int oneVertex)
{
    Edge firstEdge;
    firstEdge.from=oneVertex;
    EdgeNode * temp=G->adjList[oneVertex].firstedge;
    if(temp!=NULL)
    {
        firstEdge.to=temp->adjvex;
        firstEdge.weight=temp->weight;
    }
    else
    {
        firstEdge.to=-1;
        firstEdge.weight=-1;
    }
    return firstEdge;
}




//返回oneEdge的终点
int ToVertex(Edge oneEdge)
{
    return oneEdge.to;
}




//返回与perEdge相同顶点的下一条边
Edge NextEdge(GraphAdjList * G,Edge perEdge)
{
    Edge myEdge;
    myEdge.from=perEdge.from;
    EdgeNode * temp=G->adjList[perEdge.from].firstedge;
    while(temp!=NULL && temp->adjvex<=perEdge.to)
    {
        temp=temp->next;
    }
    if(temp!=NULL)
    {
        myEdge.to=temp->adjvex;
        myEdge.weight=temp->weight;
    }
    else
    {
        myEdge.to=-1;
        myEdge.weight=-1;
    }
    return myEdge;
}


//判断是否为边
bool IsEdge(Edge oneEdge)
{
    if(oneEdge.to==-1 )
    {
        return false;
    }
    else
    {
        return true;
    }
}





//访问当前的顶点
void Vist(GraphAdjList * G,int v)
{
    printf("%c ",G->adjList[v]);
}



//用队列实现拓扑排序
void TopsortbyQueue(GraphAdjList * G,sqQueue * Q)
{
    int i;
    QElemtype Elem;
    for(i=0;i<G->numVertexes;i++)
    {
        G->Mark[i]=UNVISITED;
    }
    for(i=0;i<G->numVertexes;i++)
    {
        if(G->Indegree[i]==0)
        {
            EnQueue(Q, i);      
        }
    }
    while(QueueLength(*Q)!=0)   //如果队列不为空
    {
        DeQueue(Q,&Elem);
        printf("%c ",G->adjList[Elem].data);
        G->Mark[Elem]=VISITED;
        for(Edge e=FirstEdge(G,Elem);IsEdge(e);e=NextEdge(G,e))
        {
            G->Indegree[ToVertex(e)]--;
            if(G->Indegree[ToVertex(e)]==0)
            {
                EnQueue(Q, ToVertex(e));    
            }
        }
    }
    for(i=0;i<G->numVertexes;i++)
    {
        if(G->Mark[i]==UNVISITED)
        {
            printf("此图有环！\n");
            break;
        }
    }
}



int main()
{
    GraphAdjList  G;
    sqQueue Q;
    InitQueue(&Q);
    int numVer,numEd;
    printf("请输入顶点数和边数：\n");
    scanf("%d%d",&numVer,&numEd);
    InitGraphAdjList(&G,numVer,numEd);
    GreateALGraph(&G);
    TopsortbyQueue(&G,&Q);
    printf("\n");
    return 0;
}