目录
一,定义:
1,有向无环图
2,拓朴排序
1,每个顶点出现且仅仅出现一次。
2,若存在一条从顶点 A 到顶点 B 的路径,那么在序列中顶点 A 出现在顶点 B 的前面。
二,DAG的性质
性质1. 从任意一个起点进行dfs,必不会陷入死循环。
性质2. 入度为0的点信息确定,删掉入度为0的点以及出边后,新的入度为0的点信息也唯一确定。
三,拓扑排序的遍历
四,例题
1,有向图的拓扑序列
使用图片理解拓扑排序(也是该图的模拟过程)
1,在不考虑边权的情况下 输入数据为:
由此建立邻接表。可得第一次入度为零的点为“1”“2” 将此两点入度
所以先将1指向的点和边删除,并将指向的点(3,4)的入度-1;得到下图
由于第一次入度为零的点还有“2”,将1删除后,点“2”还在队中,所以同上操作,得到图三
由上图得:点3的入度为零,所以按照操作将“3”入队,出队,删边,删除边指向的点的入读-1;
同上操作,此时删除点“4;则点“5”的入读=0;
经过删除。得到点六,所以存在拓扑排序,该图为DAG
2,求最长路
五,最小生成树
1,定义:
2,基本性质
1. 生成树是一个连通子图,是给定图的一个子集,它连接了所有节点且没有环。(有环可以减少一条边)
2. 生成树形态不止一种,且含有图中全部n个顶点,以及包含图中n-1条边。
3,求解方法:
1、Kruskal 复杂度:n(mlogm)
2、例题 详见下:编辑
代码:
一,定义:
1,有向无环图
如果有一个非有向无环图,且A点出发向B经C可回到A,形成一个环。将从C到A的边方向改为从A到C,则变成有向无环图。有向无环图的生成树个数等于入度非零的节点的入度积。(from baidu)
若一个有向图不存在环,则称为有向无环图【字面意思】这个东西就叫做DAG(Directed Acyclic Graph),
如图所示:
2,拓朴排序
在图论中,拓扑排序(Topological Sorting)是一个有向无环图的所有顶点的线性序列。且该序列必须满足下面两个条件:
1,每个顶点出现且仅仅出现一次。
2,若存在一条从顶点 A 到顶点 B 的路径,那么在序列中顶点 A 出现在顶点 B 的前面。
由拓朴排序的定义可知:只有DAG才有拓扑排序,其余没有拓扑排序一说。
二,DAG的性质
性质1. 从任意一个起点进行dfs,必不会陷入死循环。
性质2. 入度为0的点信息确定,删掉入度为0的点以及出边后,新的入度为0的点信息也唯一确定。
三,拓扑排序的遍历
在dij和spfa等算法中,任意点都会重复更新多次,所以会导致时间复杂度提高。在拓扑排序中,不是从起点(任意点)开始遍历,而是从入度为0的点开始遍历,这样该点就不会有其它点进行更新它。所以这样每个点和边都只会被遍历一次。
所以拓朴排序的时间复杂度为n(n+m).
拓扑排序的大致过程:
- 从 图中选择一个 入度为0的顶点并入度。
- 当该节点出队时,将该节点所指向边的节点入度-1如果新节点入度为零,则将新节点入度。
- 重复 1 和 2 直到当前图为空或当前图中不存在入度为零的顶点为止。后一种情况说明有向图中必然存在环。当所有节点都入过队列,则当前图存在拓扑排序,则该图为DAG图。
四,例题
1,有向图的拓扑序列
题目:(要求详见图)
使用图片理解拓扑排序(也是该图的模拟过程)
1,在不考虑边权的情况下 输入数据为:
6 7(点数,边数)
1 3
1 4
2 5
4 5
3 6
5 6
3 4
由此建立邻接表。可得第一次入度为零的点为“1”“2” 将此两点入度
所以先将1指向的点和边删除,并将指向的点(3,4)的入度-1;得到下图
由于第一次入度为零的点还有“2”,将1删除后,点“2”还在队中,所以同上操作,得到图三
由上图得:点3的入度为零,所以按照操作将“3”入队,出队,删边,删除边指向的点的入读-1;
同上操作,此时删除点“4;则点“5”的入读=0;
经过删除。得到点六,所以存在拓扑排序,该图为DAG
在删除边的过程中,将出队但未被删除的点存入一个vector容器。最后将该容器按照顺序输出则得到了该图的拓扑排序。
如果该容器中存下的点的数量 不等于一开始输入的点的数量,则该图不存在拓扑排序,即该图不是DAG图。
#include<bits/stdc++.h>//万能头
#pragma GCC s//日常优化
#pragma GCC optimize(2)//相信肯定有人要借鉴代码,这可不是好习惯哦,所以注释++++++
#pragma GCC optimize(3)
#pragma GCC fastusing namespace std;const int N = 2e5 + 100;//提前定义节省时间
const int M = 4e5 + 100;
int head[N], Next[M], ver[M], tot,deg[N],n,m;void add(int x, int y) {//建立邻接表ver[++tot] = y;Next[tot] = head[x];head[x] = tot;
}long long read() {//日常快读,节省时间int x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}return x*f;
}vector<int>v;
priority_queue<int,vector<int>,greater<int> > qc;//因为题目要求按照字典序最小输出,所以建立优先队列
void topsort() {//拓朴排序for (int i=1;i<=n;i++)if (!deg[i]) qc.push(i); while (qc.size()) {int x = qc.top(); qc.pop();v.push_back(x);//在出队时进行记录for (int i = head[x];i;i=Next[i]) {int y=ver[i];if (!--deg[y]) qc.push(y);} }
}int main() {int x, y;n=read();m=read();//运用快读(点的个数,边的个数)for (int i=1;i<=m;i++) {x=read();y=read();//快读+2add(x,y);deg[y]++;//将被指向的结点入度加1}topsort();//开始排序if (v.size()<n)//如果有的点没有被遍历过说明不存在拓扑排序,即不存在DAGcout <<-1;else {for(int i=0;i<v.size();i++) cout<<v[i]<< " ";}return 0;
}
2,求最长路
题目见图++;
题目分析:如果按照常规操作,这道题肯定要TLE,另外,数据范围也要注意(开小了PAC)所以,这道题只能快读+拓扑排序才能过
#include<bits/stdc++.h>//万能头文件
#pragma GCC s//O优化
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC fastusing namespace std;
const int N=5e5+5,M=3e6+5;//根据题目范围提前定义
int head[N], Next[M],ver[M],du[N],dis[M],w[M],tot,n,m;//关于结点的范围是N,和边有关的大小为M;long long read() {//快读int x=0,f=1;char c=getchar();while(!isdigit(c)) {if(c=='-') f=-1;c=getchar();}while(isdigit(c)) {x=x*10+c-'0';c=getchar();}return x*f;
}
void add(int x, int y,int z) {//建立邻接表++tot;ver[tot]=y;w[tot]=z;Next[tot]=head[x];head[x]=tot;
}
void bfs() {//开始遍历queue<int>q;for (int i=1;i<=n;i++) { if(!du[i])q.push(i);dis[i]=-2e9;}dis[1]=0;while (!q.empty()) {int x=q.front();//存下来要遍历的节点q.pop();//将该节点出队for (int i = head[x];i;i=Next[i]) {int y=ver[i];du[y]--;if(dis[x]!=-2e9){dis[y]=max(dis[y],dis[x]+w[i]);}if(!du[y]) {q.push(y);//将节点入队,等待重新遍历}} }
}
int main() {int x,y,z;n=read();//使用快读m=read();for(int i=1;i<=m;i++) {x=read();//源节点y=read();//指向的节点z=read();//边权add(x,y,z);du[y]++;//被指向的节点入度++}bfs();cout<<dis[n];//输出最大路径return 0;
}
五,最小生成树
1,定义:
最小生成树(Minimum Spanning Tree,MST)是指在连通图的所有生成树中,各边的权值之和最小的生成树。它是一个连通的无向图,其中所有顶点都连通,且没有环,边的权值之和最小。生成树是在无向连通图中,将图中所有顶点以最少的边连通的子图。即建图转化为树,用最少的边保证每个节点的连通性。
2,基本性质
1. 生成树是一个连通子图,是给定图的一个子集,它连接了所有节点且没有环。(有环可以减少一条边)
2. 生成树形态不止一种,且含有图中全部n个顶点,以及包含图中n-1条边。
3,求解方法:
1、Kruskal 复杂度:n(mlogm)
2、例题 详见下:
代码:
#include<bits/stdc++.h>//万能头文件
#pragma GCC optimize(1)//O优化
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma Gcc optinize("o1")
#pragma Gcc optinize("o2")
#pragma Gcc optinize("o3")
#pragma GCC optimize("Ofast")
using namespace std;
const int N =2e5+5;
int n,m,mst=0,fa[N],cnt=0;//记录长度之和
struct node{//运用结构体来存边,按照边权大小进行排序int u,v,w;
}pt[N];
long long read() {//日常快读int x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}return x*f;
}
bool operator<(node x,node y){//重载一下运算符,方便进行结构体比较return x.w<y.w;
}
int find(int x){if(fa[x]==x)return x;return fa[x]=find(fa[x]);
}
void kruscal(){for(int i=1;i<=n;i++) fa[i]=i;for(int i=1;i<=m;i++){int a=find(pt[i].u), b=find(pt[i].v);if(a!=b){fa[a]=b;mst+=pt[i].w;cnt++;}if(cnt==n-1) break;}
}
int main(){n=read();m=read();for(int i=1;i<=m;i++){int x,y,z;x=read();y=read();z=read();pt[i]={x,y,z};} sort(pt+1,pt+m+1);kruscal();if(cnt<n-1) cout<<"orz";else cout<<mst;
}