有向图拓扑排序

绝地灬酷狼 2022-05-22 08:27 244阅读 0赞

//
    // main.cpp
    // Tu
    //
    // Created by 李奕昕 on 2018/6/16.
    // Copyright © 2018 李奕昕. All rights reserved.
    //
    #include <iostream>
    #include <stdio.h>//注意
    #include <stdlib.h>//注意
    #include <string.h>
    using namespace std;
    #define MAX_VERTEX_NUM 20
    #define MAX_VEX 20
    #define num 100
    typedef string VertexType,VexType;
    typedef int ElemType;
    typedef int EdgeType,InfoType;
    int  Visited[MAX_VEX] ;
    
    typedef struct ArcNode{ //边（弧）结点的类型定义
        int  adjvex;   //边（弧）的另一顶点的在数组中的位置
        ArcNode *nextarc;//指向下一边（弧）结点的指针
        InfoType *info;      //该弧相关信息的指针
    }ArcNode;
    typedef struct Vnode{
       //顶点结点及其数组的类型定义
        VertexType data;    //顶点信息
        ArcNode * firstarc;    //指向关联该顶点的边（弧）链表
    } Vnode, AdjList[MAX_VERTEX_NUM];
    typedef struct {
        AdjList  vertices;
        int  vexnum, arcnum;    //图的当前顶点数和弧数
        int  kind;    //图的种类标志
    } ALGraph;    //图邻接表类型
    typedef struct
    {
        int data[num];
        int top;
    }SeqStack;
    SeqStack S;
    int indegree[num];
    void InitStack(SeqStack &S)
    {
        S.top=-1;
    }
    int StackEmpty(SeqStack S)
    {
        if(S.top==-1)
            return 1;
        else
            return 0;
    }
    int push(SeqStack &S, int  x)
    {
        if (S.top==num-1)
        {
            return 0;
        }
        S.top++;
        S.data[S.top]=x;
        return 1;
    }
    int pop(SeqStack &S,int &x)
    {
        if(S.top==-1)
        {
            return 0;
        }
        x=S.data[S.top];
        S.top--;
        return 1;
    }
    int LocateVex(ALGraph G,string v)
    {
        int i;
        for(i=0;i<G.vexnum;i++)
            if(v==G.vertices[i].data)
                return i;
        return -1;
    }
    
    void Creat(ALGraph &G)
    {
        int i,k,j;
        string v1,v2;
        ArcNode *p1;
        cin>>G.vexnum>>G.arcnum;
        for(i=0;i<G.vexnum;++i)
        {
            cin>>G.vertices[i].data;
            G.vertices[i].firstarc=NULL;
        }
        for(k=0;k<G.arcnum;++k)
        {
            cin>>v1>>v2;
            i=LocateVex(G,v1);
            j=LocateVex(G,v2);
            p1=new ArcNode;
            p1->adjvex=j;
            p1->nextarc=G.vertices[i].firstarc;
            G.vertices[i].firstarc=p1;
        }
    }
    
    void FindInDegree(ALGraph &G, int indegree[])
    {
        int k,t;
        ArcNode *p ;
        for(k=0;k<G.vexnum;k++)
            indegree[k]=0;
        for(k=0;k<G.vexnum;k++)
        {
            p=G.vertices[k].firstarc ;
            while(p!=NULL)
            {
                t=p->adjvex;
                indegree[t]++;
                p=p->nextarc ;
            }
        }
    }
    int Topologic_Sort(ALGraph G, int indegree[])
    {
        FindInDegree(G,indegree);
        InitStack(S);
        int count;
        int i=0;
        ArcNode *p;
        int k;
        string v;
        for(k=0;k<G.vexnum;k++)
            if(indegree[k]==0)
                push(S,k);
        count=0;
        while(!StackEmpty(S))
        {
            pop(S,i);
            v=G.vertices[i].data;
            cout<<v<<" ";
            count++;
            for(p=G.vertices[i].firstarc;p;p=p->nextarc)
            {
                k=p->adjvex;
                if(!--indegree[k])
                    push(S,k);
            }
        }
        if(count<G.vexnum)
            return 0;
        else return 1;}
    int main()
    {
    
        ALGraph G;
        Creat(G);
        Topologic_Sort(G,indegree);
        return 0;
    }