srcmini本文概述
生成树可以定义为连接的无向图G的子图, 该图是通过从图中删除所需数量的边而生成的树。换句话说, 生成树是将所有顶点连接在一起的连通图和无向图G的非循环子图。图G可以具有多个生成树。
最小生成树
加权图中可以为每个边分配权重。但是, 最小生成树是具有最小总权重的生成树。换句话说, 最小生成树是某个特定图的所有其他生成树中权重最小的树。
最短路径算法
在本教程的这一部分中, 我们将讨论用于计算图中两个节点之间的最短路径的算法。
为此有两种算法。
- 普里姆算法
- 克鲁斯卡尔算法
生成树可以定义为连接的无向图G的子图, 该图是通过从图中删除所需数量的边而生成的树。换句话说, 生成树是将所有顶点连接在一起的连通图和无向图G的非循环子图。图G可以具有多个生成树。
加权图中可以为每个边分配权重。但是, 最小生成树是具有最小总权重的生成树。换句话说, 最小生成树是某个特定图的所有其他生成树中权重最小的树。
在本教程的这一部分中, 我们将讨论用于计算图中两个节点之间的最短路径的算法。
为此有两种算法。
评论前必须登录！
注册