图论 最小生成树相关概念
- 连通图:在无向图中，若任意两个顶点vivi与vjvj都有路径相通，则称该无向图为连通图。
- 强连通图:在有向图中，若任意两个顶点vivi与vjvj都有路径相通，则称该有向图为强连通图。
- 连通网:在连通图中，若图的边具有一定的意义，每一条边都对应着一个数，称为权；权代表着连接连个顶点的代价，称这种连通图叫做连通网。
- 生成树: 一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。
- 最小生成树:在连通网里面,代价最小的生成树便是最小生成树
最小生成树(Prim&Kruskal)
- 实例:如电路网怎么建设成本最低
- Prim(普里姆)算法
- Prim算法可以称为加点法,每次选择代价最小的边的点,从任一顶点开始,直至覆盖所有点
- 算法思想:贪心
- 算法流程:
- 令图的所有顶点集合位V;初始令集合u={s},v=V−u
- 寻找集合u,v中可以组成最小权重边(u0,v0)并且加入到集合u中
- 重复上述步骤,直到生成n-1条边或者n个顶点为止
- 普里姆算法如图:
- Kruskal(克鲁斯卡尔)算法
- Kruskal算法可以成为加边法,初始的生成边数为0,每次迭代选择最小代价的边,加入到最小生成树的边集合里面
- 算法思想:贪心
- Kruskal算法流程:
- 将图的所有边按照代价从小到大进行排序
- 将图中的n个顶点看成n个树构成的森林
- 按照权值从小到大选择边,所选的边的两个顶点应该属于独立的树,则将它们连接成一棵树
- 重复第三步,直到全部顶点都属于一棵树,或者有n-1条边为止
- 克鲁斯卡尔算法流程:
- Prim算法对于点操作,适用于稠密图;Kruskal算法对边进行操作,适用于稀疏图
最短路径
- 路径长度:指路径所经历的边的数目
- 带权路径长度:指路径所经过的边的权值之和
- 最短路径:指带权路径值最小的路径
最短路径(Dijkstra&Floyd)
- Dijkstra(迪杰斯特拉算法):
- 用于求某点到其余各点的最短路径(只能计算权值大于0的边)
- 算法思想:
- 贪心思想
- 设存在顶点集合U、T;U中包含了已经确定的最小权值路径的点,T中包含未确定的最小权值路径的点
- 初始状态时:U中只包含了U0源点
- 接下来从T中选择距离U0权值最小的点,加入U中
- 集合U中每新增一个节点,都需要刷新U0到T中剩余元素的最小权值;新增加的U节点权值为原先权值与新增加U之后的节点的最小值
- 重复3、4步骤,直到T中的所有节点在U中
- 算法流程图:
- Floyd(弗洛伊德算法):
- 用于计算每一对顶点之间的最短距离
- 算法思想:
- 弗洛伊德算法的核心是DP,dp[i][j]=Math.min(dp[i][j],dp[i][k]+dp[k][j]);
- 弗洛伊德算法模板:
//k为中转节点 for(int k = 1; k <= n; k++) //i为开始节点 for(int i = 1; i <= n; i++) //j为结束节点 for(int j = 1; j <= n; j++) //以k中间节点,求i至j的最低代价 if(a[i][j] > a[i][k]+a[k][j]) a[i][j] = a[i][k]+a[k][j];
- Floyd算法流程:
