图论之生成树 _生成树

本文概述

最小生成树
最短路径算法

生成树可以定义为连接的无向图G的子图, 该图是通过从图中删除所需数量的边而生成的树。换句话说, 生成树是将所有顶点连接在一起的连通图和无向图G的非循环子图。图G可以具有多个生成树。
最小生成树加权图中可以为每个边分配权重。但是, 最小生成树是具有最小总权重的生成树。换句话说, 最小生成树是某个特定图的所有其他生成树中权重最小的树。
最短路径算法在本教程的这一部分中, 我们将讨论用于计算图中两个节点之间的最短路径的算法。
【图论之生成树】为此有两种算法。