【数据结构】图的应用（最小生成树、拓扑排序、最短路径等）

devtools/2024/11/15 0:38:18/

文章目录

  • 最小生成树
  • 有向无环图及其应用
    • 拓扑排序
      • 概念
      • 基于邻接表的拓扑排序算法：
      • 基于邻接矩阵的拓扑排序算法：
  • 最短路径
    • 单源点最短路径
      • 基于邻接表的Dijkstra算法
      • 输出从源点from到to的最短路径上的顶点序列
    • 每对顶点之间的最短路径
      • 基于邻接矩阵的Floyd算法
      • 输出各顶点之间的最短路径
  • 习题：

最小生成树

概念

定义：在加权连通图的所有生成树中，各边权值之和最小的生成树。

注意：（1）是无向连通图（2）最小生成树可能不唯一，但其权值之和是唯一的。

求解最小生成树的常用算法是Prim算法和Kruskal算法，都是属于贪心算法，都利用了最小生成树的MST性质。

Prim算法和Kruskal算法时间复杂度分别是O(n2)和O(eloge)

Prim算法

Prim算法是一种基于顶点的贪心算法，从起始顶点出发，每次迭代选择当前可用的最小权值边，然后把边上依附的其他顶点加入最小生成树。

Prin算法又称为“加点法”，比较适合稠密图。

在这里插入图片描述

算法描述如下：
G=(V,E)是一个加权连通图，T=(U,TE)是G的一颗最小生成树。
（1）最小生成树T的初始状态为U={u0},TE={}，此时图中只有一个起始顶点，边集为空。
（2）在所有u∈U，v∈V-U边中找到一条代价最小的边(u,v)，把边(u,v)并入生成树的边集TE中，同时v并入 生成树的顶点集U中。
（3）重复步骤二，直至U=V。此时TE中必有n-1条边，T=（U,TE）为G的最小生成树。

基于邻接表的Prim算法：

template <class VertexType, class EdgeType>
void adjList<VertexType, EdgeType>::prim(EdgeType noEdge) const{struct Dist{int adjVex;		//最小代价边衣服的顶点编号EdgeType lowCost;		//最小代价}*D=new Dist[verNum];edgeNode *p;	//p 用于遍历边EdgeType minCost;		//minCost 用于保存最小的代价int u, i, j,count=0;	//u 是当前顶点，i、j 是循环中的计数器，count 是计数器，用于记录生成树的边数。for(i=0; i<verNum; ++i){visited[i]=false;D[i].lowCost=noEdge;}u=0;	//初始化uvisited[u]=true;for(i=1;i<verNum;++i){		//选中一个点u加入D中for(p=verList[u].firstEdge;p!=NULL;p=p->next)	//更新u关联的顶点的D值if(!visited[p->to] && D[p->to].lowCost > p->weight){D[p->to].lowCost=p->weight;		//更新lowCostD[p->to].adjVex=u;				//更新adjVex}minCost=noEdge;for(j=0;j<verNum;++j)	//在V-U中找lowCost最小顶点uif(D[j].lowCost<minCost){minCost=D[j].lowCost;u=j;}TE[count].vex1=D[u].adjVex;	TE[count].vex2=u;			//保存最小生成树的一条边TE[count++].weight=D[u].lowCost;D[u].lowCost=noEdge;		//顶点u已经=并入D中visited[u]=true;}delete [] D;
}

基于邻接矩阵的Prim算法

template <class VertexType, class EdgeType>
void adjMatrix<VertexType, EdgeType>::prim(EdgeType noEdge) const{struct Dist{int adjVex;		//最小代价边衣服的顶点编号EdgeType lowCost;		//最小代价}*D=new Dist[verNum];EdgeType minCost;int u, i, j,count=0;for(i=0; i<verNum; ++i){visited[i]=false;D[i].lowCost=noEdge;}u=0;	//初始化uvisited[u]=true;for(i=1;i<verNum;++i){		//选中一个点u加入D中for(j=0;j<verNum;j++)	//更新u关联的顶点的D值if(!visited[j] && edges[u][j]!=noEdge){if(edges[u][j]<D[j].lowCost){D[j].lowCost=edges[u][j];		//更新lowCostD[j].adjVex=u;				//更新adjVex}}minCost=noEdge;for(j=0;j<verNum;++j)	//在V-U中找lowCost最小顶点uif(D[j].lowCost<minCost){minCost=D[j].lowCost;u=j;}TE[count].vex1=D[u].adjVex;	TE[count].vex2=u;			//保存最小生成树的一条边TE[count++].weight=D[u].lowCost;D[u].lowCost=noEdge;		//顶点u已经=并入D中visited[u]=true;}delete [] D;
}

Kruskal算法

Kruskal算法是一种基于边的贪心算法，初始时生成树包含所有顶点，边集为空，每次迭代选择当前可用的最小权值边，且该边加入生成树的边集中不会产生环，直到所有顶点都能连通。

Kruskal算法又称为"加边法"，比较适合稀疏图。

在这里插入图片描述

算法描述如下：
G=(V,E)是一个加权连通图，T=(U,TE)是G的一颗最小生成树。
（1）最小生成树T的初始状态为U=V，TE={}，此时T中有图G中的所有顶点，边集为空，所以每个顶点字自成一个连通分量。
（2）在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入TE中，否则舍去此边而选择下一条代价最小边。
（3）重复步骤二，直到T中所有顶点都在同一连通分量上。

基于邻接表的Kruskal算法：

template <class VertexType, class EdgeType>
void adjList<VertexType, EdgeType>::kruskal const{int count=0;mstEdge e;edgeNode *p;unionFindSet S(verNum);		//并查集SpriorityQueue<mstEdge> Q;		//优先级队列Qfor(int i=0; i<verNum;++i){		//用图中的边生成优先级队列for(p=verList[i].firstEdge;p!=NULL;p=p->next)if(i<p->to){		//防止重复入队e.vex1=i;e.vex2=p->to;e.weight=p->weight;Q.enQueue(e);	//边e入队}}while(count<verNum-1){		//选出verNum-1条边e=Q.deQueue();		//从优先级队列中出队一条边int u=S.find(e.vex1);		//查找顶点vex1所属子集int v=S.find(e.vex2);		//查找顶点vex2所属子集if(u!=v){					//边上的两个顶点不属于同一连通分量S.merge(u,v);		//合并u、v所属子集（连通分量）TE[count++]=e;		//保存最小生成树中的一条边}}
}

基于邻接矩阵的Kruskal算法：

template <class VertexType, class EdgeType>
void adjList<VertexType, EdgeType>::kruskal const{int count=0;mstEdge e;edgeNode *p;unionFindSet S(verNum);priorityQueue<mstEdge> Q;for(int i=0; i<verNum;++i){		//用图中的边生成优先级队列for(int j=i+1;j<verNum;j++)		//从j=i+1开始，防止重复入队if(edges[i][j]!=noEdges){e.vex1=i;e.vex2=j;e.weight=edges[i][j];Q.enQueue(e);}}while(count<verNum-1){		//选出verNum-1条边e=Q.deQueue();			//从优先级队列中出队一条边int u=S.find(e.vex1);int v=S.find(e.vex2);if(u!=v){S.merge(u,v);TE[count++]=e;}}
}

有向无环图及其应用

拓扑排序

概念

AOV网络：在有向图中，用顶点表示活动或任务或任务间的优先关系。
拓扑序列：在有向无环图中，若存在顶点Vi到Vj的路径，那么在序列中顶点Vi排在顶点Vj的前面。
拓扑排序：将有向无环图的顶点按照它们之间的优先关系拍成一个拓扑序列的操作

拓扑排序可以解决先决条件问题

步骤：
（1）在有向图中任选一个入度为0的顶点并输出它。
（2）删除该顶点及该顶点的所有出边，将其邻接点的入度减1.
重复上述步骤，最后有两种可能的情况
（1）当输出了有向图的全部顶点时，排序成功。
（2）当图中还有顶点没有输出，则排序失败，说明图中含有环。

算法思想：
关键是如何找到入度为0的顶点，以及如何删除该顶点的所有出边。
（1）计算每个顶点的入度，存入inDegree数组中，然后遍历inDegree数组，将所有入度为0的顶点入队。
（2）若队列非空，从队首出队一个入度为0的顶点并输出它，将以该顶点为尾的所有邻接点的入度减1，若此时某个邻接点的入度为0，则将其入队。
（3）重复步骤二。

基于邻接表的拓扑排序算法：

template <class VertexType, class EdgeType>
bool adjList<VertexType, EdgeType>::topSort()const{queue<int> q;edgeNode *p;int i,curNode,count=0;int *intDegree = new int[verNum];for(i=0;i<verNum;i++)inDegree[i]=0;for(i=0;i<verNum;i++){	//遍历边表，求顶点入度for(p=verList[i].firstEdge;p!=p->next)++inDegree[p->to];}for(i=0;i<verNum;i++)if(inDegree[i]==0)q.push(i);	//入度为0的顶点入队列while(!q.empty()){curNode=q.front();q.pop();	//出队一个入度为0的顶点cout<<verList[curNode].vertex<<' ';	//输出该顶点topOrder[count]=curNode;	//保存拓扑序列，用于求关键路径count++;for(p=verList[curNode].firstEdge;p!=NULL;p=p->next)if(--inDegree[p->to]==0)	//邻接点入度减1q.push(p->to);		//入度为0的顶点入队列}cout<<endl;if(count==verNum)	//输出全部顶点，拓扑排序成功return true;return false;		//该有向图有环，拓扑排序失败
}

基于邻接矩阵的拓扑排序算法：

template <class VertexType, class EdgeType>
bool adjList<VertexType, EdgeType>::topSort()const{queue<int> Q;int i,j,curNode,count=0;int *intDegree = new int[verNum];for(i=0;i<verNum;i++)inDegree[i]=0;for(i=0;i<verNum;i++){	//遍历邻接矩阵，求顶点入度for(j=0;j<verNum;j++)if(edges[i][j]!=noEdge)++inDegree[i]=0;}for(i=0;i<verNum;i++)if(inDegree[i]==0)Q.push(i);	//入度为0的顶点入队列while(!Q.empty()){curNode=Q.front();Q.pop();	//出队一个入度为0的顶点cout<<vertexs[curNode]<<' ';	//输出该顶点count++;				//计数器+1for(j=0;j<verNum;++j){if(edges[curNode][j]!=noEdge)	//邻接点入度减1if(--deDegree[j]==0)Q.push(j);		//入度为0的顶点入队列}}cout<<endl;if(count==verNum)	//输出全部顶点，拓扑排序成功return true;return false;		//该有向图有环，拓扑排序失败
}

最短路径

单源点最短路径

在一个带权有向图G=(V,E)中，每条边上的权值都是非负实数，给定顶点s∈V充当源点，计算从源点到其他各顶点的最短路径。

Dijkstra(迪杰斯特拉算法)是一种按路径长度递增的次序产生到各顶点最短路径的贪心算法。
步骤如下：
（1）初始化D、pre和visited数组，D[i]置为无穷大∞，pre[i]置为-1,visited[i]置为false.源点到自身的距离D[0]置为0，源点的前驱pre[0]置为0.
（2）从尚未确定最短路径长度的集合V-S中取出一个最短路径长度最小的顶点Vk，将Vk加入集合中，置visited[k]为ture.
（3）修改数组D中由源点s经过Vk可达的最短路径长度。若加进Vk作为中间顶点，使得源点s到Vi∈V-S的最短路径长度变短，则修改D[i]和pre[i]，即当D[i]>D[j]+weight(vk+vi)时，置D[i]=D[j]+weight(vk+vi)，pre[i]=k。
（4）重复步骤二三，直到V=S。数组D记录了从源点s到图中其他顶点的最短路径长度。

Dijkstra算法的时间复杂度O(n2)

基于邻接表的Dijkstra算法

求从源点start到其他顶点的最短路径

template <class VertexType, class EdgeType>
bool adjList<VertexType, EdgeType>::dijkstra(int start, EdgeType noEdge) const{ if (start < 0 || start > (this->verNum - 1) ) //源点下标越界return false;EdgeType* D = new EdgeType[this->verNum];	//记录到各顶点的最短路径的长度int* pre = new int[this->verNum];	//edgeNode* p;EdgeType min;int i;int j;int k;for (i = 0;i < this->verNum;++i) {this->visited[i] = false;D[i] = noEdge;pre[i] = -1;}D[start] = 0;pre[start] = start;min = D[start];k = start;for (i = 1;i < this->verNum;++i) {this->visited[k] = true;for (p = verList[k].firstEdge;p != NULL;p = p->next) {if (!this->visited[p->to] && D[p->to] > (min + p->weight)) {D[p->to] = min + p->weight;pre[p->to] = k;}}    min = noEdge;k = start;for (j = 0;j < this->verNum;++j) {if (!this->visited[j] && (D[j] < min)) {k = j;min = D[k];}}if (k != start) {printDijPath(start,k,pre);cout << " : " << D[k] << endl;}        }delete []D;delete []pre;return true;
}

输出从源点from到to的最短路径上的顶点序列

template <class VertexType, class EdgeType>
void adjList<VertexType, EdgeType>::printDijPath(int from, int to, int pre[]) const{  if (from == to) {cout << verList[from].vertex;return;}printDijPath(from,pre[to],pre);cout << "->" << verList[to].vertex ;
}

每对顶点之间的最短路径

Floyd算法步骤如下：
（1）初始化D矩阵和pre矩阵，若Vi到Vj没有弧，则D[i][j]=∞，pre[i][j]=-1 ; 若i=j,则 D[i][j]=0, pre[i][j]=i；若Vi到Vj存在弧，则 D[i][j]=weight(Vi,Vj) ，pre[i][j]=i.
（2）对于每一个顶点Vk，若 D[i][k]+D[k][j]<D[i][j] 成立,表明从Vi到Vk再到Vj的路径比原来Vi到Vj的路径短，则置D[i][j]=D[i][k]+D[k][j]，pre[i][j]=pre[k][j]
（3）将图中的n个顶点依次加入每对顶点之间进行探测，也就是对矩阵D和矩阵pre进行n次更新，最终矩阵D中记录的便是每对顶点之间的最短路径的长度。

基于邻接矩阵的Floyd算法

template <class VertexType, class EdgeType>
void adjMartrix<class VertexType, class EdgeType>::floyd() const{EdgeType **D=new EdgeType*[verNum];int **pre=new EdgeType*[verNum];int i,j,k;for(i=0;i<verNum;++i){D[i]=new EdgeType[verNum];pre[i]=new int[verNum];for(j=0;j<verNum;++j){D[i][j]=(i==j)?0:edges[i][j];pre[i][j]=(edges[i][j]=noEdge)?-1:i;}}for(k=0;k<verNum;++k)for(i=0;i<verNum;++i)for(j=0;j<verNum;j++)if(D[i][j]!=noEdge && D[k][j]!=noEdges && D[i][k]+D[k][j]<D[i][j]){D[i][j]=D[i][k]+D[k][j];pre[i][j]=pre[k][j];}printFloyd(D,pre);for(i=0;i<verNum;++i){delete []D[i];delete []pre[i];}delete []D;delete []pre;
}

输出各顶点之间的最短路径

template <class VertexType, class EdgeType>
void adjMatrix<VertexType, EdgeType>::printFloyd(EdgeType **D, int **pre) const{int i, j, k;cout<<"shortest path:\n";for(i=0;i<verNum;i++){for(j=0;j<verNum;++j)cout<<D[i][j]<<'\t';cout<<endl;}cout<<"precurosr of vertex:\n";for(i=0;i<verNum;++i){for(j=0;j<verNum;++j)cout<<pre[i][j]<<'\t';cout<<endl;}
}

习题：

1.判断一个有向图是否由环，除拓扑排序方法外，还可以用（）
A.深度优先遍历
B.广度优先遍历
C.求最短路径
D.求关键路径

选A。


http://www.ppmy.cn/devtools/26788.html

相关文章

ubuntu系统搭建pytorch环境详细步骤【笔记】

ubuntu系统搭建pytorch环境详细步骤【笔记】

实践设备&#xff1a;华硕FX-PRO&#xff08;NVIDIA GeForce GTX 960M&#xff09; 搭建PyTorch环境的详细步骤如下&#xff1a; 1.安装Ubuntu系统&#xff1a; 下载Ubuntu的镜像文件并制作启动盘。将启动盘插入计算机&#xff0c;启动计算机并按照提示安装Ubuntu系统。 2.…
阅读更多...
mac 初始环境搭建

mac 初始环境搭建

首先是jdk 我用的是1.8版本 去oracle官网。直接安装。1.8 的jdk。 这是链接。 一、准备安装包 苹果的mac book目前常见的有两种芯片的 一种是intel芯片的&#xff0c;一种是Apple Silicon的。为了更好的体现不同芯片的性能&#xff0c;各种开发工具包给出了不同的实现&am…
阅读更多...
【介绍下Unity编辑器扩展】

【介绍下Unity编辑器扩展】

&#x1f308;个人主页: 程序员不想敲代码啊 &#x1f3c6;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f44d;点赞⭐评论⭐收藏 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共…
阅读更多...
十一、大模型-Semantic Kernel与 LangChain 的对比

十一、大模型-Semantic Kernel与 LangChain 的对比

Semantic Kernel 与 LangChain 的对比 Semantic Kernel 和 LangChain 都是用于开发基于大型语言模型&#xff08;LLM&#xff09;的应用程序的框架&#xff0c;但它们各有特点和优势。 基本概念和目标 Semantic Kernel 是一个由微软开发的轻量级 SDK&#xff0c;旨在帮助开发…
阅读更多...
Spark Structured Streaming 分流或双写多表 / 多数据源（Multi Sinks / Writes）

Spark Structured Streaming 分流或双写多表 / 多数据源（Multi Sinks / Writes）

博主历时三年精心创作的《大数据平台架构与原型实现&#xff1a;数据中台建设实战》一书现已由知名IT图书品牌电子工业出版社博文视点出版发行&#xff0c;点击《重磅推荐&#xff1a;建大数据平台太难了&#xff01;给我发个工程原型吧&#xff01;》了解图书详情&#xff0c;…
阅读更多...
BPMN2.0 事件 - 基本概念

BPMN2.0 事件 - 基本概念

事件Event是BPMN2.0执行语义中重要的概念，是流程运行过程中发生的对象，会影响流程的流转。 从不同的角度来看，事件有不同的分类。从流程生命周期角度定义，事件可以分为开始，中间，结束三种类型，从事件的动作处理，触发方式角度定义，事件又分为捕获，抛出事件。还有很多…
阅读更多...
聊聊 ASP.NET Core 中间件（一）：一个简单的中间件例子

聊聊 ASP.NET Core 中间件（一）：一个简单的中间件例子

前言&#xff1a;什么是中间件 服务器在收到 HTTP 请求后会对用户的请求进行一系列的处理&#xff0c;比如检查请求的身份验证信息、处理请求报文头、检查是否存在对应的服务器端响应缓存、找到和请求对应的控制器类中的操作方法等&#xff0c;当控制器类中的操作方法执行完成…
阅读更多...
梯度提升回归（概念+实例）

梯度提升回归（概念+实例）

目录 前言 一、基本概念 1. 弱学习器&#xff08;Weak Learners&#xff09; 2. 提升&#xff08;Boosting&#xff09; 3. 梯度提升算法&#xff08;Gradient Boosting Algorithm&#xff09; 3.1. 梯度下降 3.2. 回归问题中的梯度提升 4. 梯度提升回归的训练过程 5.…
阅读更多...
最新文章

Copyright @ 2022~2023