C++图笔记(三)有向无环图(及最小生成树(略))以及剩下的排序

ops/2024/11/14 3:20:57/

目录

一,定义:

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).

拓扑排序的大致过程:

  1. 从 图中选择一个 入度为0的顶点并入度。
  2. 当该节点出队时,将该节点所指向边的节点入度-1如果新节点入度为零,则将新节点入度。
  3. 重复 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;
}


http://www.ppmy.cn/ops/96702.html

相关文章

内网数据带外传输及隧道建立

内网数据带外传输及隧道建立 使用TCP套接字外泄数据&#xff08;易被检测&#xff09;使用ssh进行渗透使用http(s)进行渗透建立http协议隧道使用ICMP进行数据外泄使用ICMP建立C2通信通过DNS进行数据外泄通过DNS进行c2通信通过DNS进行隧道传输 使用TCP套接字外泄数据&#xff08…

MySQL——单表查询(二)按条件查询(4)空值查询

在数据表中&#xff0c;某些列的值可能为空值(NULL),空值不同于0&#xff0c;也不同于空字符串。 在 MySQL 中&#xff0c;使用 IS NULL 关键字来判断字段的值是否为空值,其语法格式如下所示&#xff1a; SELECT * |字段名 1,字段名 2,... FROM 表名 WHERE 字段名 IS …

SpringCloud天机学堂:分布式任务调度

SpringCloud天机学堂&#xff1a;分布式任务调度 文章目录 SpringCloud天机学堂&#xff1a;分布式任务调度1、分布式任务调度2、分布式任务调度原理3、分布式任务调度技术对比4、XXL-JOB介绍部署调度中心定义任务注册执行器配置任务调度执行一次 1、分布式任务调度 一般的定时…

探索Python性能优化的神秘力量:Line Profiler

文章目录 探索Python性能优化的神秘力量&#xff1a;Line Profiler第一部分&#xff1a;背景第二部分&#xff1a;库简介第三部分&#xff1a;安装指南第四部分&#xff1a;基本使用方法第五部分&#xff1a;实际应用场景场景1&#xff1a;数据分析场景2&#xff1a;机器学习模…

【C++】模拟实现vector

可以把vector看作升级版的数组&#xff0c;可采用下标进行访问&#xff0c;非常高效&#xff0c;大小可动态改变&#xff0c;会自动扩容&#xff0c;数据存储在堆空间上。 VECROR 成员变量、函数及模板总览构造函数和析构函数无参构造函数构造n个元素大小的空间并初始化通过某个…

ubuntu18.04下安装nvidia3090显卡驱动

前言&#xff1a;之前安装过4090的显卡&#xff0c;但是是使用20.04直接在第三方驱动里面安装的&#xff0c;这回使用的是18.04&#xff0c;版本估计是21年以前的&#xff0c;附加驱动直接没有&#xff0c;整整卡了两天&#xff0c;最后再查询多篇资料后最终安装好&#xff0c;…

计算机视觉实战详解:从基础到前沿

引言: 计算机视觉是人工智能领域中最激动人心的分支之一。它赋予机器以"眼睛",使其能够理解和处理视觉信息。本专栏旨在带领读者从基础知识出发,逐步深入计算机视觉的核心概念和实际应用,最终掌握前沿技术。无论您是初学者还是有一定基础的开发者,这个专栏都将为您提…

使用PowerShell自动化Windows系统管理任务(上)

使用PowerShell自动化Windows系统管理任务是一个广泛而深入的主题&#xff0c;它涵盖了从简单的日常任务到复杂的系统维护和优化策略。PowerShell作为Microsoft提供的强大脚本和自动化工具&#xff0c;已经成为Windows系统管理员不可或缺的一部分。在本文中&#xff0c;我们将深…