图论在数据结构中是非常有趣而复杂的,作为web码农的我,在实际开发中一直没有找到它的使用场景,不像树那样的频繁使用,不过还是准备
仔细的把图论全部过一遍。
一:最小生成树
图中有一个好玩的东西叫做生成树,就是用边来把所有的顶点联通起来,前提条件是最后形成的联通图中不能存在回路,所以就形成这样一个
推理:假设图中的顶点有n个,则生成树的边有n-1条,多一条会存在回路,少一路则不能把所有顶点联通起来,如果非要在图中加上权重,则生成树
中权重最小的叫做最小生成树。
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLicmbw5iM5ITMzIDOxITMyEjMxAjMvwVM0cDNxIzLcJTMwIzLcNXZnFWbp9CXt92YuM3ZvxmYuNmLyADMjlGcvw1LcpDc0RHaiojIsJye.png)
对于上面这个带权无向图来说,它的生成树有多个,同样最小生成树也有多个,因为我们比的是权重的大小。
二:prim算法
求最小生成树的算法有很多,常用的是prim算法和kruskal算法,为了保证单一职责,我把kruskal算法放到下一篇,那么prim算法的思想
是什么呢?很简单,贪心思想。
如上图:现有集合m={a,b,c,d,e,f},再设集合n={}。
第一步:挑选任意节点(比如a),将其加入到n集合,同时剔除m集合的a。
第二步:寻找a节点权值最小的邻节点(比如f),然后将f加入到n集合,此时n={a,f},同时剔除m集合中的f。
第三步:寻找{a,f}中的权值最小的邻节点(比如e),然后将e加入到n集合,此时n={a,f,e},同时剔除m集合的e。
。。。
最后m集合为{}时,生成树就构建完毕了,是不是非常的简单,这种贪心做法我想大家都能想得到,如果算法配合一个好的数据结构,就会
如虎添翼。
三:代码
1. 图的存储
图的存储有很多方式,邻接矩阵,邻接表,十字链表等等,当然都有自己的适合场景,下面用邻接矩阵来玩玩,邻接矩阵需要采用两个数组,
①. 保存顶点信息的一维数组,
②. 保存边信息的二维数组。
2:矩阵构建
矩阵构建很简单,这里把上图中的顶点和权的信息保存在矩阵中。
3:prim
要玩prim,我们需要两个字典。
①:保存当前节点的字典,其中包含该节点的起始边和终边以及权值,用weight=-1来记录当前节点已经访问过,用weight=int.maxvalue表示
两节点没有边。
②:输出节点的字典,存放的就是我们的n集合。
当然这个复杂度玩高了,为o(n2),寻找n集合的邻边最小权值时,我们可以玩玩avl或者优先队列来降低复杂度。
4:最后我们来测试一下,看看找出的最小生成树。