|
什么是拓扑排序呢？就是将一个有向无环图中所有顶点在不违反先决条件关系的前提下排成线性序列的过程称为拓扑排序。 学拓扑排序有什么用呢？当然有用啦~。比如说学校排课的时候，会考虑到有的课程需要先修。我们学完C程序设计这门课，有了编程基础，然后才能学习数据结构。大学要修很多门课程的，人为的去排课很头痛的，这时候就可以用拓扑排序解决这个问题。 拓扑排序只针对有向无环图(DAG)，有两种方法可以实现，一种是队列实现，另外一种是深搜(DFS)实现。 这里先介绍队列实现的方法。 （1）从图中选择任意一个入度为0的顶点且输出 （2）从图中删掉此顶点及所有的出边，将其入度减少1 （3）回到第（1）步继续执行  我们对上面图进行拓扑排序，我这里采用的是邻接表储存图，贴代码。
#include
#include
#include
using namespace std;
class Graph
{
int v; //顶点个数
vector *adj; //邻接表
int *indegree; //每个顶点的入度
public:
Graph(int n); //构造函数
~Graph(); //析构函数
void addEdge(int start,int end); //添加边
void TopsortbyQueue(); //拓扑排序
};
Graph::Graph(int n)
{
v=n;
adj=new vector[n];
indegree=new int[n];
for(int i=0;i |