拓扑排序
claran_ran_away · · 个人记录
拓扑排序：
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
听起来可能会比较蒙，说的简洁一点就是：
上图拓扑排序后输出为：袜子 内裤 鞋 裤子 衬衣 腰带 领带 夹克 换成字母就是 D A E B F C G H(结果不一定相同，有序正常即可)
这就是拓扑排序(区别于普通的升降序排序算法)
实现思想：
- 从 DAG 图中选择一个 没有前驱（即入度为0）的顶点并输出
- 从图中删除该顶点和所有以它为起点的有向边
- 重复 1 和 2 直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止
代码实现：
1. 输入：
一般输入n列,每列2个数，第一个数表示所表示结点，第二个数为指向结点；
2. 输出：
排好序（拓扑）的数
（图片及代码引用如上网址）
一般我们解决拓扑排序的方法多半是用二维数：
#include <bits/stdc++.h>
#define MAXV 100
int map[MAXV][MAXV];//存放边的信息
int indegree[MAXV];//存放入度
void topo_sort(int n)
{
int i,j,k;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(indegree[j]==0)//当前入度为0
{
indegree[j]--;
printf("%d ",j);//输出，既从图中去除
for(k=1;k<=n;k++)
{
if(map[j][k]==1)
//它本来指向的顶点的入度减一
indegree[k]--;
}
break;
}
}
}
int main()
{
int n,m;
scanf("%d %d",&n,&m);//n为顶点数，m为边数
memset(map,0,sizeof(map));
memset(indegree,0,sizeof(indegree));
int i;
int x,y;
for(i=0;i<m;i++)
{
scanf("%d %d",&x,&y);
if(!map[x][y])
{
map[x][y]=1;
indegree[y]++;
}
}
topo_sort(n);
return 0;
but！！！德莫！！！
我们还可以用vector和小根堆来实现
那什么是vector呢？小根堆又是啥？
小根堆(优先队列（倒序版）)
所属头文件：<queue>
小根堆，就是优先队列的倒序版。（堆：准确来说是经过排序的完全二叉树，为了便于理解就这样说明吧~）
优先队列（堆）:
与队列名字和头文件一样，但是压入的数会自动以降序的方式存储；小根堆则为升序。
小根堆的创建：
#include <iostream>
#include <queue>
using namespace std;
int main(){
priority_queue<int,vector<int>,greater<int> > q;//创建小根堆
return 0;
}注意！！！第5行的尖括号绝对不能挨在一起！！
vector __变常数组
所属头文件： <vector>
#include <bits/stdc++.h>
using namespace std;
int main(){
voctor <int> v;
v.push(1);
v.push(2);
v.push(5);
cout << v.size() << endl;
cout << v[1] << endl;
for(int i = 0;i <= v.size();i++) cout << v[i] << " ";
return 0;
}
创建v时，相当于创建了一个可控大小的数组
加一个数自动开辟空间（或删）
那么——vector 如何存储 图？
首先我们要知道：图在一维数组中的表示方法：
如图，“结点”即为数组下标，表示结点；“入度”即为数组存储的数据，表入度 因此vector也如图储存。
那么也想之前一样的思路：
vector<int> top_sort(){
priority_queue<int ,vector<int> ,greater<int > >Q;//一定记得尖括号要分开哦
for(int i=1;i<=n;i++){
if(!indeg[i]){
Q.push(i);
}
}
vector<int> TOP;
while(!Q.empty()){
int T=Q.top();
Q.pop();
indeg[T]=-1;
TOP.push_back(T);
for(auto &e:graph[T]){
indeg[e]--;
if(indeg[e]==0)Q.push(e);
}
}return TOP;
}
}以上就是主要思路部分~