一个有 n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的权值和边最小
一、最小生成树的应用
生成树和最小生成树有许多重要的应用。
例如:要在n个城市之间铺设光缆,主要目标是要使这 n 个城市的任意两个之间都可以通信,但铺设光缆的费用很高,且各个城市之间铺设光缆的费用不同,因此另一个目标是要使铺设光缆的总费用最低。这就需要找到带权值的最小生成树。
构建最小生成树时最常用的方法就是prim算法和kruskal算法
二、图的入度和出度
1.构建图的邻接矩阵
以上图中的图结构为例,由于图是顶点与顶点之间的连接关系,又带有权值,所以我们可以用邻接矩阵来表示图中顶点的关系
- 矩阵中的值代表顶点与顶点之间的权值,由于示例是一个无向图,所以这个矩阵是以对角线对称的
- 我们可以将矩阵看成一个二维数组,因此就可以很容易的创建出这个图的数据结构了
1 | int[] graph0 = new int[]{0, 10, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 11, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT}; |
2.入度与出度
- 顶点的出边条数称为该顶点的出度
- 顶点的入边条数称为该项点的入度
- 则在矩阵中某个点的入度和出度即为横向和纵向的有效权值个数
1 | /** |
三、prim(普里姆)算法
算法思路:
- 定义一个临时的一维数组,用于存放可用的连接边,数组下标为顶点序号,值为权值
- 任选一个点作为起点,以起点的所有权值对数组进行初始化
- 找出数组中最小权值的边,即为最小生成树中的一条有效边
- 将找到的最小边在数组中赋值为0,代表已经使用过。并将数组与找到顶点的所有边进行比较,若顶点的边的权值比当前数组存放的可用边的权值小,则进行覆盖
- 重复循环2,3,4的操作直至遍历完所有顶点
算法代码:
1 | /** |
下图是画的一个针对此代码运行的流程图(画了半天发现在文章中显示的比较小,如果看起来觉得小的同学可以下载原图后放大观看)
- 绿色代表一维数组中存放的可用最小边
- 红色代表找到的最小生成树的边
四、kruskal(克鲁斯卡尔)算法
算法思路:
- 现将所有边进行权值的从小到大排序
- 定义一个一维数组代表连接过的边,数组的下标为边的起点,值为边的终点
- 按照排好序的集合用边对顶点进行依次连接,连接的边则存放到一维数组中
- 用一维数组判断是否对已经连接的边能构成回路,有回路则无效,没回路则是一条有效边
- 重复3,4直至遍历完所有的边为止,即找到最小生成树
首先将所有边按权值进行排序
定义一个边的对象
1 | /** |
按照排序的图对边进行初始化
1 | Edge edge0 = new Edge(4, 7, 7); |
最小生成树算法代码:
1 | /** |
下图是画的一个针对此代码运行的流程图
- 红色代表找到的最小生成树的边
- 蓝色代表找到的边但是是回环则无效