用克鲁斯卡尔算法将下列的图构造成最小生成树，画出生成过程。

[问答题]

张小头

取n个顶点且无边的非连通图T={V,{}}，此时每个顶点自成一个连通分量。

按照规则：

1.每次从小到大选取权值最小的边，该边的两个顶点满足在不同的连通分量上，加入到T中

2.当选取的边连接的两个顶点在同一个连通分量的时候，舍弃该边，选取权值相同或者次小的满足条件1的边

（这里需要搞懂连通分量的概念，这里取自百度：在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。如果图中任意两个顶点之间都连通，则称该图为连通图，否则，将其中的较大连通子图称为连通分量。　　在有向图中，如果对于每一对顶点vi和vj，从vi到vj和从vj到vi都有路径，则称该图为强连通图；否则，将其中的极大连通子图称为强连通分量。）

比如为什么不选取2-5这条边，因为0-5 0-2这两条边已经连上了，2可以通过0到5，所以2和5连通，属于同一个连通分量，所以在1-5 2-5 的选择中，就舍弃2-5这条边。

发表于 2021-02-19 18:53:07 回复(0)