青海建设工程信息网站,坯子库登录成wordpress,北京100强公司排行榜,民和县公司网站建设本文包含了图的基本概念 1.相关概念
1.1 无/有向
无向图#xff1a;每一个顶点之间的连线没有方向
有向图#xff1a;连线有方向#xff08;类似离散数学的二元关系 A,B代表从A到B的边#xff0c;有方向#xff09;
A,B中A为始点#xff0c;B为终点在…本文包含了图的基本概念 1.相关概念
1.1 无/有向
无向图每一个顶点之间的连线没有方向
有向图连线有方向类似离散数学的二元关系 A,B代表从A到B的边有方向
A,B中A为始点B为终点在无向图中(V,U)和(U,V)是同一条边
1.2 顶点和边
图中的节点叫做顶点。
顶点之间的线条就是边表示事物与事物之间的关系。 1.3 自回路/多重图 1.4 完全图
图中每一个顶点都有连线有最多的边数就叫做完全图
设顶点为N个
无向完全图中n(n-1)/2条边有向完全图中n(n-1)条边
1.5 邻接与关联
无向图中(u,v)是一条边
顶点u和v邻接边(u,v)与顶点u和v相关联
1.6 子图 图中G3是G1的子图G4是G2的子图
简单说来就是子图是原图的一部分包括顶点、边注意方向都是原图中的一部分
1.6 路径
路径是顶点序列
路径是一个节点到另外一个节点需要经过的边
路径长度路径上边的数目简单路径除起点、终点可以相同外路径中其余顶点不相同回路起点和重点相同的简单路径
1.7 连通图
两个顶点之间只要有路径那就是连通的
连通图无向图中任意两点之间都有路径那么就是一个连通图连通分量无向图的极大连通子图 注意虽然连通分量被称为“极大连通子图”但它并不是节点最多的哪一个。比如上图中的G2和G3都是极大连通子图。 强连通图有向图中如果两个顶点之间U和V之间有U到V的路径那就一定有从V到U的路径强连通分量有向图的极大联通子图 强连通图G1的极大强连通分量就是它自己只有非强连通图才有多个强连通分量
上图中G2就不是强联通图因为4节点没有入边也就没有节点能到4
第三图的上半部分并非G1的强连通分量但是是G2的强力连通分量。同时单独的4顶点也是一个强连通分量单独顶点都是
1.7 顶点的度
度与该顶点相关联的边的数目
入度射入v的边的数目出度从v射出去的边的数目
1.8 生成树
生成树包含图中的所有顶点但是只有足够构成一颗树的n-1条边
因为n-1条边再加上一条就会构成回路生成树中不包含回路
1.9 网
给图中的每条边都添加上权值带权的图称为网
2.表示法
2.1 邻接矩阵
用二维数组来表示每个顶点之间的关系矩阵 优缺点
优点
便于判断两个顶点之间是否有边可以直接根据下标判断O(1)便于计算各个顶点的度 无向图第i行元素之和就是顶点i的度前提是用1来表示有向图第i行元素之和为顶点i的出度第i列为入度
缺点
如果节点多边少就会出现空间浪费无法方便地找到一个顶点和那一条边相连需要遍历对于无向图也会出现空间浪费
2.2 邻接表
邻接表有些类似于哈希表的拉链法。每一个节点后面跟着一个单链表用于存储与这个节点相连的节点。
在G2的有向图中一般存储的是出度表即从该节点出发的边。如果边有权值则还需要存储权值 优缺点
优点
可以快速找到一个节点和谁相连出度
缺点
不便于判断两个顶点之间是否有边不便于计算有向图各个顶点的度需要遍历所有节点
关于第二个缺点可以新增一个入度表即一个出度表/一个入读表来计算。但是这样会增加时空复杂度。
3.遍历
3.1 深度优先DFS
深度优先以递归为基本思路从一个结点开始递归向后遍历这个节点的单链表中的节点。 为了避免同一个节点遍历多次我们需要有一个bool数组来标识一个节点是否遍历过。如果遍历过则把对应下标的值设定为true来标识
由于深度优先的递归部分只能遍历连通图。若出现了上图中非联通的情况需要我们在外循环中重新遍历一下bool标识数组确认所有节点都遍历完成。
如果漏了节点就是没有和其他节点联通的独立节点那么就以此节点开头再进行一次深度遍历。 3.2 广度优先BFS 广度优先遍历类似二叉树的层序遍历依靠循环队列来完成遍历
入起始节点打印起始节点的值出队头节点第一次的时候是起始节点往队列中入该节点单链表中的所有节点依此类推出一个节点就入这个节点单链表中的所有节点同样地用一个bool数组标识节点是否被访问。如果被访问了则跳过该节点也需要在队列循环结束后遍历一遍bool数组确认所有节点都访问完毕。 3.3 判断一个图是否连通
使用任何遍历方式遍历完毕后检查bool数组
若有节点没有被访问则说明是非连通图
4.拓扑排序 https://blog.csdn.net/qq_43448856/article/details/119959241 给定一个图每次都选择一个无入度没有入边的节点加入序列中并删除该节点的出边
最终得到的序列就是一个拓扑排序之后的序列
每次删除出边后都可能形成新的无入度的节点
因此针对同一棵树的拓扑排序序列可能有多种不同的情况
5.最小生成树算法
生成树的概念参考 1.8 生成树最小生成树即让生成树中所有边的权值加起来最小
5.1 普里姆Prim 如图中所示我们先根据这个树的结构构造三个数组
nearest代表和这个节点最近的节点默认为-1lowcost代表和这个节点最近节点的权值默认为无穷大mark是一个bool数组标识该节点是否已经加入到最小生成树
当我们每从图中取出一个节点的时候就需要更新这三个表
如图当我们取走0之后就需要更新和0连通的三个节点其中nearest代表刚刚删除掉的节点0lowcost代表它们和0相连边的权值同时要把mark中0改为true表明0已经加入生成树了 第二次选取的时候遍历lowcost表找到权值最小的边为(0,2)权值为1。此时就把2加入进去并更新与2相连的节点3注必须要权值更小才需要更新 依次遍历直到所有节点都加入了最小生成树左下角的图 该算法的时间复杂度为O(N^2)只与节点的数量N有关
5.2 克鲁斯卡尔Kruskal 构建一个和原图一样的节点图无边在原图中查找权值最小的边判断其节点是否已经相同如果没有形成环则加入到最小生成树的图中 判断是否成环可以通过并查集解决 如下图先遍历所有边发现(0,2)的权值最小判断该边加入后并不会使生成树形成环则加入该边
下图中(0,2)之间的边1已经移动到了T图上同时将0和2加入到同一个并查集的合集内 同理继续找权值最小的边加入到生成树中。如下将3边移动到右图。 此时我们遇到了3条权值最小的边权值都为5。此时可以随便加入一条边即可不能使生成树成环
如下图中(0,3)和(2,3)的边加入后会使图成环不能选择该边
并查集中0、2、3、5已经在一个集合中此时判断(0,3)在一个集合该边不能加入(2,3)在一个集合中该边不能加入 应该选择(1,2)这条边其不会让树成环 此时所有边都已经连起来了最小生成树生成成功
算法分析 该算法的时间复杂度为O(E*logE)其中E为边的数目
6.最短路径
带权有向图中把一条路径仅考虑简单路径上所经边的权值之和定义为该路径的路径长度
从源点到终点可能不止一条路径把路径长度最短的那条路径称为最短路径
6.1 单源最短路径
思路有些类似并查集path数组中存放的是每一个节点的上一条路径若下标1处存放0则代表是从0走到1。同时d数组中标识从0走到下标1的长度。 把1加到s序列之后发现0到节点2的路径长度缩短了从原本的(0,2)的6变成了现在(0,1)(1,2)的415长度缩短对应d数组中下标2处也需要更新
继续下去直到U数组中没有节点S数组中节点满即可获得一个从0出发到任何节点的单源最短路径 6.1.1 狄克斯特拉算法Dijkstra
求解单源最短路径问题的算法
前提给定一个带权有向图G和源点v限定各边上的权值大于等于0
基于定理最短路径上的顶点的最短路径就是该路径 理解现有一条v到u的最短路径v-……-a-u那么v到a的最短路径即为v-……-a 算法思路
把图G中的顶点集合V分成两部分
第一部分为已求出最短路径的顶点集合用S表示初始时S中只有一个源点以后每求得一条最短路径v……u就将u加入到集合S中直到全部顶点都加入到S中算法结束
第二部分为其余未求出最短路径的顶点集合用U表示
过程
初始化S只包含源点即S{v}v的最短路径为0。U包含除v以外的其他顶点U中顶点i距离为边上的权值若v与i直接相连或∞v与i不是直接相连 从U中选取一个距离v最小的顶点u把u加入S中该选定的距离就是v到u的最短路径长度 以u为新考虑的中间点修改U中各顶点i的最短路径长度 若从源点v到顶点 i的最短路径长度经过顶点u比原来最短路径长度不经过顶点u短则修改顶点 i的最短路径长度 重复2、3步直至所有顶点都包含在S中
代码设计
着重解决两个问题
如何存放最短路径长度
用一维数组d[i]存储。源点v默认d[i]表示源点到顶点i的最短路径长度 如d[2]12表示源点到顶点2的最短路径长度为12 如何存放最短路径
用一维数组path[]存储。path数组中所存储的数组代表当前顶点在最短路径中的前驱顶点 如path[3]1表示在最短路径中顶点3的前驱顶点是顶点1 算法演示 这是初始化状态
发现数组d中顶点1距离源点距离最近那么就将顶点1加入到S中 这时我们需要更新剩余点的最短路径长度和最短路径
显然顶点23456并不会都做更新。只有与顶点1直接相连的顶点才有可能会受影响。在上图中会受影响的为顶点2和顶点4 原本顶点2的最短路径长度是6最短路径是0,2。现在由于顶点1的引入最短路径长度变为5最短路径变为0,1,1,2
顶点4同理
至此就完成了一次顶点的引入。下面重复上述操作至所有顶点都在S中即可
下面是全过程 总结一下在更新d和path数组时只有与本次引入S中的顶点i直接相连的后驱顶点才有可能发生改变其余顶点是不可能变的
现在我们利用d和path数组来求解最短路径长度和最短路径
求源点0到终点6的最短路径长度
即为d[6]的值为16
求0到6的最短路径 从终点往源点找
时间复杂度
时间复杂度为 O(n2)
