拓扑排序(代码理解)
程序员文章站
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
*/
上一篇: 拓扑排序核心代码
下一篇: MYSQL 行转列优化