最小生成树第一弹之“简介”

    好久没有写文章了，今天先简单聊下“最小生成树”的相关知识。当然，这也是为我们接下来学习最小生成树的两个经典算法做铺垫。

    设G=(V,E)表示一个无向连通图，它有n个顶点。那么它的子图t=(V,E1)是它的一棵生成树(spanning tree)当且仅当t是一棵树。

    这里要注意下，生成树包含了原先该无向连通图的所有顶点，从原先的边集E中挑选(n-1)条边连接这n个顶点。

    举个简单的例子：

一个无向图及它的三个生成树

    当然，上述例子还有其它的生成图，这里小编就不列举出来。

    生成树的应用场景之一是基于生成树的一个性质：最小生成树（Minimum Spanning Tree，简称MST）。

    举个例子：

一个图及它的最小生成树

    在上图中，顶点数N=7，那么该图的最小生成树在这些边中选择N-1条出来，连接所有的N个顶点，同时这N-1条边的边权之和是所有方案中最小的。

    由于最小生成树的定义包含了需要选出一个边的子集，因此这个问题属于子集范例问题。

    关于最小生成树的两个算法，接下来小编再写写文章来分享。