欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

拓扑排序(代码理解)

程序员文章站 2024-03-19 12:08:04
...

把代码段看完应该就可以了,网上的也挺多的;
我的代码已经够容易理解的了;

#include <iostream>
#include <queue>
#include<cstdio>
#include <cstring>
using namespace std;
queue<int> q;
const int E=100;//E为最大边数
const int N=100;//n为最大定点数
struct Edge {
    int u; //起点 
    int v; //终点 
    int next;//上一条边在edge数组中的位置 
} edge[E];//图 
int head[N];//记录输入的最后一个起始节点在edge数组中的位置 
int num;//数组下标;
int indegree[N];
int n, m;
void init()
{
    memset(head, 0, sizeof(head));//所有节点的初始为0,一开始节点没有与之相连的边 
    num=1;//数组下表从1开始 
    memset(indegree, -1, sizeof(indegree));
}
void add_edge(int from,int to)
{
    edge[num].u = from;//起点
    edge[num].v = to;//终点
    edge[num].next=head[from];//记录以from节点出发的上一条边在edge数组的位置 
    head[from]=num;  //更新以from节点出发的在edge数组的位置 
    num++; //数组下标+1 
    indegree[to]++;
}

bool TopologicalSort(int indegree[])
{
    int i,k;
    for(i=0;i<n;i++)
    {
        if(indegree[i] == -1)//如果入度为-1,那么入队 
        {
            q.push(i);
        }
    }
    int count = 0;
    while(!q.empty())
    {
        k = q.front();
        q.pop();
        cout<<k<<"-->";
        count++;//记录个数 
        for(int i = head[k];i != 0;i = edge[i].next)  
        {
            indegree[edge[i].v]--;//删除入度 
            if(indegree[edge[i].v] == -1){
                q.push(edge[i].v);
            }
        }
    }
    if(count<n)//如果个数小于总数,那么有回路 
        return false;
    return true;
}

int main()
{
    int a,b;
    init();
    scanf("%d %d",&m, &n); //m为边数,n为定点数,默认从1开始 
    for(int i=1;i<=m;i++)
    {                    
          scanf("%d %d",&a,&b);   //a是起点,b是终点 
          add_edge(a,b);//存储信息 
    }
    if(TopologicalSort(indegree))
        cout<<"正常完成!"<<endl;
    else 
        cout<<"该有向图有回路!"<<endl;
    return 0;
}
/*测试数据
11 7
0 1
0 2
0 3
1 2
1 4
2 4
2 5
3 5
4 6
5 4
5 6

测试数据2
7 5
0 2
0 3
1 2
1 3
2 4
3 2
3 4 
*/