拓扑排序

//
//  main.c
//  toposort
//
//  Created by 毛遵杰 on 2019/12/13.
//  Copyright © 2019 毛遵杰. All rights reserved.
//


#include <stdio.h>
#define MAX 100
 
typedef char VertexType;
 
typedef struct ArcNode {
     int adjvex;
     struct ArcNode *next;
     int weight;
}ArcNode;
 
typedef struct VertexNode {
    VertexType data;
    ArcNode *firstArc;
}VertexNode,AdjVerList[MAX];
 
typedef struct {
    AdjVerList vertices;
    int vexnum,arcnum;
}ALGraph;
 
int indegree[MAX];
 
void CreateALGraph(ALGraph *G);
void Display(ALGraph *G);
int TopoSort(ALGraph *G);

int main()
{
    ALGraph G;
    CreateALGraph(&G);
    //Display(&G);
    TopoSort(&G);
    return 0;
}
 
//vertex position
int LocateVex(ALGraph *G,VertexType v)
{
    int i;
    for(i=0;i<G->vexnum;i++)
    {
        if(G->vertices[i].data == v)
            return i;
    }
    return -1;
}
 

void CreateALGraph(ALGraph *G)
{
    VertexType v1,v2;
    int w;
    ArcNode *Arc;
 
    printf("please enter the vertex and arc");
    cin>>G->vexnum>>G->arcnum;
 
 
    printf("please enter data of vertex:");
    for(int i=0;i<G->vexnum;i++){
        cin>>G->vertices[i].data;
        G->vertices[i].firstArc = NULL;
    }
 
    printf("enter %d The two vertices corresponding to the group edges and their weights, separated by spaces:\n",G->arcnum);
    for(int k=0;k<G->arcnum;k++) {
        cin>>v1>>v2>>w;
        int i = LocateVex(G,v1);
        int j = LocateVex(G,v2);
        Arc = new ArcNode;
        Arc->adjvex = j;
        Arc->weight = w;
        Arc->next = G->vertices[i].firstArc;
        G->vertices[i].firstArc = Arc;
    }
}
 
void Display(ALGraph *G)
{
    ArcNode *p;
    printf("numbering，  vertex, Vertices of adjacent edges\n");
    for(int i=0;i<G->vexnum;i++)
    {
        printf("%d,%d,%d",i,t,G->vertices[i].data);
        for(p=G->vertices[i].firstArc;p!=NULL;p=p->next)
            printf("t",p->adjvex);
        printf("\n");
    }
}
 
 

void FindIndegree(ALGraph *G)
{
    int i;
    ArcNode *p;
    
    for(i=0;i<G->vexnum;i++)
        indegree[i] = 0;
 
    for(i=0;i<G->vexnum;i++)
    {
        p = G->vertices[i].firstArc;
        while(p)
        {
            
            indegree[p->adjvex]++;
            p = p->next;
        }
 
        
    }
}
 


int TopoSort(ALGraph *G)
{
    printf("A topological sorting result of the directed graph is:");
    stack<int> s;
    ArcNode *p;
    int i,k;
    FindIndegree(G);
    
    for(i=0;i<G->vexnum;i++)
    {
        
        if(indegree[i]==0)
            s.push(i);
    }
    
    int count = 0;
    while(!s.empty())
    {
        i = s.top();
        s.pop();
        printf("%d",G->vertices[i].data);
        count++;
        
        p = G->vertices[i].firstArc;
        while(p!=NULL)
        {
            k = p->adjvex;
            indegree[k]--;
            if(indegree[k]==0)
                s.push(k);
            p = p->next;
        }
    }
    
    if(count<G->vexnum)
        return -1;
    else
        return 0;