拓扑排序代码

参考网址  https://blog.csdn.net/ywcpig/article/details/52599867

拓扑排序

核心思想

(1)从有向图中选取一个没有前驱(即入度为0)的顶点，并输出之;

(2)从有向图中删去此顶点以及所有以它为尾的弧;

重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。

//date:2020.4.21
//author:https://blog.csdn.net/ywcpig/article/details/52599867
#include<bits/stdc++.h>
#define MAX_VERTEX_NUM 26
using namespace std;
//图用邻接表存储
typedef struct ArcNode
{
    int adjvex;
    struct ArcNode *nextarc;
    ArcNode()
    {
        nextarc=NULL;
    }
} ArcNode;

typedef struct VNode
{
    int data;
    ArcNode *firstarc;
    VNode()
    {
        firstarc=NULL;
    }
} VNode,AdjList[MAX_VERTEX_NUM];

typedef struct
{
    AdjList vertices;
    int vexnum,arcnum;
} ALGraph;//

bool TopologicalSort(ALGraph G,int *indegree)
{
    stack<int> s;
    int i,k;
    for(i=1; i<G.vexnum+1; i++)
    {
        if(!indegree[i])
            s.push(i);
    }//将每个入度为0的结点入栈

    int count=0;
    ArcNode *p;
    while(!s.empty())
    {
        i = s.top();
        s.pop();//访问栈中的结点
        cout<<G.vertices[i].data<<"->";
        count++;
        for(p=G.vertices[i].firstarc; p; p=p->nextarc)//访问该节点的邻接链表
        {
            k = p->adjvex;
            indegree[k]--;//访问完结点的入度减1
            if(!indegree[k])//如果入度为0，入栈
                s.push(k);
        }
    }
    if(count<G.vexnum)
        return false;
    return true;
}

int main()
{
    int i;
    ALGraph g;
    cout<<"载入图中..."<<endl;
    ifstream fin("in.txt");
    fin>>g.vexnum>>g.arcnum;
    for(i=1; i<g.vexnum+1; i++)
        g.vertices[i].data = i;

    int b,e;
    ArcNode *p;
    int *indegree = new int[g.vexnum+1];
    //注意 int *a=new int(n);  申请一个整型变量空间，赋初值为n，并定义一个整型指针a指向该地址空间
    //int *indegree=(int *)malloc(sizeof(int)*(g.vexnum+1));
    memset(indegree,0,sizeof(int)*(g.vexnum+1));
    for(i=1; i<g.arcnum+1; i++)
    {
        fin>>b>>e;
        cout<<"第"<<i<<"条边："<<b<<"->"<<e<<endl;

        p = new ArcNode();
        p->adjvex = e;
        p->nextarc = g.vertices[b].firstarc;
        g.vertices[b].firstarc = p;
        indegree[e]++;
    }

    if(TopologicalSort(g,indegree))
        cout<<"正常完成！"<<endl;
    else
        cout<<"该有向图有回路！"<<endl;

    return 0;
}

两组测试数据  建立in.txt文本文件即可
1）有环

4 4
1 2
2 3
3 4
4 2

2）无环

12 16
1 2
1 3
2 3
1 4
3 5
4 5
11 6
5 7
3 7
3 8
6 8
9 10
9 11
9 12
10 12
1 12

　　

图的存储需要再次复习熟练