离散数学最小生成树怎么求
1个回答
展开全部
最小生成树是指从一个给定的连通网络中,选择若干条边,使得所选边的权值之和最小,而且这些边连接了所有的顶点,形成一棵树。
离散数学中求最小生成树的方法有Prim算法和Kruskal算法。
Prim算法:
1. 从图中任意选择一个顶点作为起始顶点,将其加入到最小生成树中;
2. 在未被加入最小生成树的顶点中,找出一条权值最小的边,将该边的另一个顶点加入到最小生成树中;
3. 重复步骤2,直到最小生成树中包含了所有的顶点。
Kruskal算法:
1. 将图中所有的边按照权值从小到大的顺序排列;
2. 从权值最小的边开始,依次选择边加入到最小生成树中,但是要保证加入的边不会形成环;
3. 重复步骤2,直到最小生成树中包含了所有的顶点。
离散数学中求最小生成树的方法有Prim算法和Kruskal算法。
Prim算法:
1. 从图中任意选择一个顶点作为起始顶点,将其加入到最小生成树中;
2. 在未被加入最小生成树的顶点中,找出一条权值最小的边,将该边的另一个顶点加入到最小生成树中;
3. 重复步骤2,直到最小生成树中包含了所有的顶点。
Kruskal算法:
1. 将图中所有的边按照权值从小到大的顺序排列;
2. 从权值最小的边开始,依次选择边加入到最小生成树中,但是要保证加入的边不会形成环;
3. 重复步骤2,直到最小生成树中包含了所有的顶点。
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询