2023年考研数据结构图的必背算法及知识点

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

1.最小生成树：
无向连通图的所有生成树中有一棵边的权值总和最小的生成树
1.1 问题背景：
假设要在n
个城市之间建立通信联络网，则连通n
个城市只需要n—1条线路。这时，自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通信网。在每两个城市之间都可以设立一条线路，相应地都要付出一定的经济代价。n
个城市之间，最多也许设立n(n-1)/2条线路，那么，如何在这些也许的线路中选择n-1条，以使总的花费最少呢?
1.2 分析问题（建立模型）：
可以用连通网来表达n
个城市以及n
个城市间也许设立的通信线路，其中网的顶点表达城市，
边表达两城市之间的线路，
赋于边的权值表达相应的代价。对于n
个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。即无向连通图的生成树不是唯一的。连通图的一次遍历所通过的边的集合及图中所有顶点的集合就构成了该图的一棵生成树，对连通图的不同遍历，就也许得到不同的生成树。
图 G5无向连通图的生成树 为(a)、(b)和(c)图所示：
G5G5的三棵生成树
：可以证明，对于有n
个顶点的无向连通图，无论其生成树的形态如何，所有生成树中都有且仅 ...

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：数据结构 考研数据 结构图 知识点 最小生成树