当前位置: 首页 > news >正文

王道数据结构6.2(图的应用)

图的应用

  • 一、最小生成树
    • (一)什么是最小生成树?
    • (二)求最小生成树算法
      • (1)prim算法
      • (2)Kruskal算法(克鲁斯卡尔)
  • 二、最短路径问题
    • (一)单源最短路径问题
      • (1)BFS算法(无权图)
      • (2)Dijkstra算法(带权图、无权图)
    • (二)多源最短路径问题— Floyd算法(带权图、无权图)

一、最小生成树

(一)什么是最小生成树?

  1. 对于一个带权连通无向图G=(V,E),生成树不同,每棵树的权(即树中所有边上的权值之和)也可能不同。设R为G的所有生成树的集合,若T为R中边的权值之和最小的生成树,则T称为G的最小生成树。
  2. 一个连通图的生成树包含图的所有的顶点,并且只尽可能少的边,对于生成树而言,若砍去它的一条边,则生成树变成非连通图,若给它增加一条边,则会形成图中的一条回路。
  3. 只有连通图才有生成树,非连通图只有生成森林。
  4. 如果一个连通图本身就是一棵树,则其最小生成树就是它本身。
  5. 最小生成树不是唯一的,但是当各个边的权值互不相同时,最小生成树是唯一的,若无向连通图的边数比顶点少1,即本身就是一个树,则最小生成树就是它自身。
  6. 最小生成树的权值总和却是唯一的,是最小的。

(二)求最小生成树算法

  1. 都是基于贪心算法的策略。
  2. 总体思路:确定顶点集合中有关的边,寻找到最小代价边(u,v),判断加入集合后会不会产生回路,若不会,则为最小生成树的一员。

(1)prim算法

  1. 思路:从某一个顶点开始构建生成树,每次将代价最小的新顶点纳入生成树,直到所有顶点都纳入为止。
int dist[n],state[n],pre[n];
dist[1] = 0;
for(i : 1 ~ n)
{
    t <- 没有连通起来,但是距离连通部分最近的点;
    state[t] = 1;
    更新 dist 和 pre;
}

  1. 时间复杂度:O(|V|2),适合于稠密图。
  2. 算法实现,以图示为例:
    请添加图片描述
    (1)首先从V0开始,构建两个表,分别是isjoin[]:记录各个结点是否已经加入树,初始时,v0为true,其他为false;lowCost[]:各个节点加入树的最低代价。
    (2)如图所示:lowCost数组的意思:小集团中只有v0存在的情况下,v1到v0最少需要6,v2到v0需要5,v3需要1,而v45没有连通,为∞。
    (3)对比lowCost数值,得到v3最小,则修改isjoin[3]=true,并且将lowCost更新为:v1可以于v3连通为5,5<6,则改为5,v2可以有4/5,则填入4,v3仍为1,v4为6,v5为4,总之lowCost为054164,扫描一遍lowCost数组选择false中最小的,即v2/v5。
    (4)重复以上过程,直到isjoin所有都变成true。

(2)Kruskal算法(克鲁斯卡尔)

  1. 思路:每次选择一条权值最小的,使者条边的两头连通(原本连通的就不选),直到所有结点都连通。
  2. 时间复杂度:O(|E|log2|E|),适用于边稀疏图。
  3. 算法实现过程:
    请添加图片描述
    (1)如图所示,首先对所有的边进行大小排序
    (2)第一轮:检查第一条边的两个顶点是否连通(是否属于同一个集合,意思是,初始的时候所有顶点都是独自成为一个集合,都不互相连通,当选取顶点以后,被选择的顶点就属于一个集合,并且连在一起,其他顶点保持不变),如果顶点不是一个集合,则选择存入被选中集合,即选择(v0,v3)(v2,v5)(v1,v4)(v2,v3)而到(v3,v5)时,由于借助v2实现了连通,则跳过不建立集合,如下图所示,类似的后序寻找请添加图片描述
    (3)一共需要执行e轮,每轮判断两个顶点是否属于同一个集合,需要O(log2e),总时间复杂度为O(elog2e)

二、最短路径问题

(一)单源最短路径问题

(1)BFS算法(无权图)

  1. 类似于广度优先遍历算法
  2. 代码:
#include <stdio.h>
#define MaxVertexNum 100
typedef char VertexType;
typedef int EdgeType;
int Max = 0x3f3f3f3f;

typedef struct {
	VertexType Vex[MaxVertexNum];
	EdgeType EdgeType[MaxVertexNum][MaxVertexNum];
	int vexnum, arcnum;
} Gragh;

//BFS遍历
bool visited[MaxVertexNum];
void BFSTraverse(Graph G) {
	for (int i = 0; i < G.vexnum; ++i)
		visited[i] = false;
	InitQueue(Q);
	for (int i = 0; i < G.vexnum; ++i)
		if (!visited[i])
			BFS(G, i);

}

void BFS(Graph G, int v) {
	visit(v);
	visited[v] = true;
	Enqueue(Q, v);
	while (!isEmpty(Q)) {
		DeQueue(Q, v);
		for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w))
			if (!visited[w]) {
				visit(w);
				visited[w] = true;
				EnQueue(Q, w);
			}
	}
}
//BFS求单源最短路径
void BFS_MIN_Distance(Graph G, int u) {
//d[i]表示从u到i结点的最短路径
	for (int i = 0; i < G.vexnum; i++){
		d[i] = Max; //初始化路径为无穷
		path[i]=-1;//最短路径从哪个顶点过来
		}
	visited[u] = true; 
	d[u] = 0;
	EnQueue(Q, u);
	while (!isEmpty(Q)) {
		DeQueue(Q, u);//队头元素u出队
		for (w = FirstNeighbor(G, u); w >= 0; w = NextNeighbor(G, u, w))//找到和它相邻的所有结点+
			if (!visited[w]) {//w为u的尚未访问的邻接顶点
				visited[w] = true;//设已访问的标记
				d[w] = d[u] + 1;//路径长度+1
				path[w]=u;//最短路径应该是从u到v
				EnQueue(Q, w);//顶点w入队
			}//if
	}//while
}

  1. 过程:从2号顶点开始
    ① 首先初始化d和path和visited数组
    队列:NULL
12345678
d[]
path[]-1-1-1-1-1-1-1-1
visited[]falsefalsefalsefalsefalsefalsefalsefalse

② 修改起始节点的数组,并且将2结点压入队列中
队列:2

12345678
d[]0
path[]-1-1-1-1-1-1-1-1
visited[]falsetruefalsefalsefalsefalsefalsefalse

③ 非空进入while循环,取出队首元素2,判断与2相连的所有结点:1,6,1结点的visited为false,1的d[]数组改为1+d[2],并且path[1]=2,表示与结点2距离为1,并且最短路径中前驱是2,并且将1压入队列;6号结点同理,6的d[]数组改为1+d[2]=1,并且path[6]=2,visited[6]=true,并且将6压入队列
队列:1、6

12345678
d[]0
path[]-1-1-1-1-11-1-1
visited[]falsetruefalsefalsefalsetruefalsefalse

④ 取出队首1,判断1的连通未访问的顶点为5,则5的d[5]改为d[1]+1=1+1=2,path[5]=1,visited[5]=1,入队
队列:6、5

12345678
d[]02
path[]-1-1-1-111-1-1
visited[]falsetruefalsefalsetruetruefalsefalse

⑤ 判断6 判断5即可得到
队列:1、6

12345678
d[]10232123
path[]2-1631267
visited[]truetruetruetruetruetruetruetrue

得到上述表格,问2到8的路径=d[8]=3,路径逆向思维进行寻找,8前为7,7前为6,6前为2,得到:2->6->7->8
4. 分析:广度优先生成树其实层数就反映了到达其他节点的最短路径,换句话说,利用广度优先构造的最小生成树,高度一定是最小的。

(2)Dijkstra算法(带权图、无权图)

  1. BFS算法的局限性:BFS算法只适合于不带权或带权值都相同的情况,如果带权权值不同则会出现错误。
  2. 过程:
    ① 初始化三个数组:final[] (标记各顶点是否已找到最短路径)、dist[] (最短路径长度)、path[](路径上的前驱)。
v0v1v2v3v4
final[]××××
dist[]0105
path[]-10-1-10

如图所示:当前可以确定的是v0可以到v4,可以到v1,分别是5,10,写入数组,并且修改path1,4的前驱为0 。
② 第一轮,循环遍历所有结点,找到目前还没有确定最短路径,且dist最小的顶点v,令final[i]=ture。如本题,最小dist为4的5,即可以说明v0到v4的最短路径为5,修改final[4]=√,并且检查所有和v4相邻的顶点,寻找有没有可能v0经过v4到其他点路径更近,发现v0v4v1长度为5+3=8<10=v0v1,所以让dist[1]=8,同理dist[2]=5+9=14,path[2]=4,dist[3]=7,path[3]=4。

v0v1v2v3v4
final[]×××
dist[]081475
path[]-14440

③第二轮,随后检查所有final值为false的顶点的,发现目前dist最小的是7,则处理3顶点,让final为√,表示已经可以确定v0->v3最短为7,且路径为0->4->3,然后检查所有v0经过v3到达的顶点vi,修改得

v0v1v2v3v4
final[]××
dist[]081375
path[]-14340

④ 检查所有final值为×的结点,选择1,更新后检查v4,v2,因为v4之前已经确定了,所以无需检查只要看v2即可,
⑤ 一直到final值全部为√。

v0v1v2v3v4
final[]
dist[]08975
path[]-14140
  1. 分析
    (1)代码思路:以从v0开始为例,初始时
final[0]=ture;dist[0]=0;path[0]=-1;
final[k]=false;dist[k]=arcs[0][k];path[k]=(arcs[0][k]==)?-1:0;

(2)需要经过n-1轮循环,循环遍历所有结点,找到还没有确定最短路径,且dist最小的顶点vi,令final[i]=true。检查所有邻接自vi的顶点,对于邻接自vi的顶点vj,若final[j]==false且dist[i]+arcs[i][j]<dist[j],则令dist[j]=dist[i]+dist[i][j],path[j]=i。
(3)时间复杂度:由于每一轮都要扫描所有数组,数组长度为n顶点个数,并且还要扫描邻接矩阵,则O(2n)~O(n),因为要扫描n-1轮,则时间复杂度为O(n(n-1)~O(n2)
(4)和prim算法很是相似,时间复杂度也是相似的
(5)注意:如果带权图中权值有负数,则这个算法将会出错,不适用。

(二)多源最短路径问题— Floyd算法(带权图、无权图)

相关文章:

  • Spring-IOC配置(XML格式)-分块简化
  • 【代码】js闭包
  • cadence SPB17.4 - allegro - 区域规则设置 - 以smd_pin_to_smd_pin为例
  • 在 Qt 中实现变色的图标(tintColor)
  • MIKE水动力笔记14_数字化海图3之提取任意等深线
  • qml中的一些常用技巧
  • 红黑树,B树、B+树、MySQL索引面试题
  • 基于Vue+Element-ui开发的一个“月日组件”,并发布npm包
  • gRPC RPC技术demo
  • 记录一下ts学习整理的一些知识点
  • java计算机毕业设计基于安卓Android的急救服务APP
  • MyBatis Plus (四) --------- 条件构造器 EntityWrapper
  • 神经网络算法应用案例,神经网络是机器算法吗
  • 2023中国(江西)国际餐饮品牌连锁加盟展览会2月26日开幕
  • Java ServiceLoader、Spring SpringFactoriesLoader、SPI方式解耦第三方组件
  • @jsonView过滤属性
  • 【402天】跃迁之路——程序员高效学习方法论探索系列(实验阶段159-2018.03.14)...
  • 0x05 Python数据分析,Anaconda八斩刀
  • JavaScript HTML DOM
  • JavaScript类型识别
  • java中具有继承关系的类及其对象初始化顺序
  • puppeteer stop redirect 的正确姿势及 net::ERR_FAILED 的解决
  • Sublime Text 2/3 绑定Eclipse快捷键
  • TypeScript迭代器
  • VUE es6技巧写法(持续更新中~~~)
  • Webpack 4x 之路 ( 四 )
  • 程序员最讨厌的9句话,你可有补充?
  • 短视频宝贝=慢?阿里巴巴工程师这样秒开短视频
  • 如何用Ubuntu和Xen来设置Kubernetes?
  • 微信公众号开发小记——5.python微信红包
  • 想晋级高级工程师只知道表面是不够的!Git内部原理介绍
  • 正则学习笔记
  • python最赚钱的4个方向,你最心动的是哪个?
  • 进程与线程(三)——进程/线程间通信
  • #使用清华镜像源 安装/更新 指定版本tensorflow
  • #周末课堂# 【Linux + JVM + Mysql高级性能优化班】(火热报名中~~~)
  • (07)Hive——窗口函数详解
  • (1)(1.13) SiK无线电高级配置(六)
  • (1)Android开发优化---------UI优化
  • (Java)【深基9.例1】选举学生会
  • (ros//EnvironmentVariables)ros环境变量
  • (仿QQ聊天消息列表加载)wp7 listbox 列表项逐一加载的一种实现方式,以及加入渐显动画...
  • (附源码)springboot宠物管理系统 毕业设计 121654
  • (十) 初识 Docker file
  • (一)使用IDEA创建Maven项目和Maven使用入门(配图详解)
  • (轉貼) 寄發紅帖基本原則(教育部禮儀司頒布) (雜項)
  • .net core 连接数据库,通过数据库生成Modell
  • .NET Core、DNX、DNU、DNVM、MVC6学习资料
  • .NET 中使用 TaskCompletionSource 作为线程同步互斥或异步操作的事件
  • .NET连接MongoDB数据库实例教程
  • /deep/和 >>>以及 ::v-deep 三者的区别
  • @converter 只能用mysql吗_python-MySQLConverter对象没有mysql-connector属性’...
  • [ C++ ] 继承
  • [2018-01-08] Python强化周的第一天
  • [2021]Zookeeper getAcl命令未授权访问漏洞概述与解决