简介
在前几个学期学习离散数学和数据结构的时候学习过图论的基本知识，这个学期学通信网络基础时候把一些算法又学了一遍。其中Prim算法的描述稍有差异，以下对这两种描述进行简要介绍，并说明其等价性。
描述一：集合版本
数据结构课程中多采用此种描述。例子引自：知乎-Prim算法——最小生成树。
具体内容
- 用两个集合A{}, B{}分别表示找到的点集和未找到的点集；
- 以A中的点为起点a，在B中找一个点为终点B，这两个点构成的边(a,b)应为其余边中最小的；
- 重复2，直至B中点集为空，A中点集为满。
算法例子
描述二：权值矩阵版本
以下的这段描述看似复杂，实际上只是讲得稍微啰嗦了一点。
主要的区别，在于用权值矩阵一个数据结构就表达了描述一中的集合A、B，以及边的权重。可能代码实现起来会更方便吧。
具体内容
- 写出图G的权值矩阵；
- 由点v 1 v_{1}v1开始，在行1中找出最小元素w 1 j w_{1j}w1j；
- 在行1和行j中，剔除列1和列j的元素，并在这两行余下的元素中找出最小元素，如w j k w_{jk}wjk（如有多个最小元素可任选其中一个）；
- 在行1、行j和行k中，圈去列1、列j和列k的元素，并在这三行余下的元素中找出最小元素；
- 直至矩阵中所有元素均被圈去，即找到图G的一棵最小生成树。
算法例子
用描述2的方式解描述1的同一道题，便于理解两种描述实际上讲的是同一个东西。
总结
通过例子可以看出找到的生成树是一样的，实际上两种描述显然是等价的。
- 描述1中的集合A、B；在描述2中体现为未被划掉的、已被划掉的元素(实际上是这些元素所在的行/列)。
- 描述1中，以A中节点a为起点，以B中节点b为终点；在描述2中体现为寻找行i中的元素w i j w_{ij}wij。
胡言乱语
实际上，你愿意倒着来的话，按描述2做法，但是将划掉某列改成划掉某行，显然也是能做的。换成描述1就等于以A中节点a为终点，以B中节点b为起点的做法。
补充1：Dijkstra算法
不同于用于求解最小生成树的Kruscal算法和Prim算法。Dijkstra算法和Prim算法是用于求解最短路径问题的。
如上图，Dijkstra算法运行一次就可以获得某一点v i v_{i}vi到其他所有点G − { v i } G-\{v_{i}\}G−{vi}的所有最短路径(故称之单源最短路径)。这是其与Floyd算法的不同之处
具体内容
- 对于图G GG，选定源节点v i v_{i}vi，G p = { v i , } G_{p}=\{v_{i}, \}Gp={vi,}；
- 维护一个列表l i s t 1 list1list1，记录v i v_{i}vi到∀ v j ∈ G − G p \forall v_{j}\in G-G_{p}∀vj∈G−Gp的距离d ( v i , v j ) d(v_{i}, v_{j})d(vi,vj)；
- 对于∀ v j ∈ G − G p \forall v_{j}\in G-G_{p}∀vj∈G−Gp，查询m i n d ( v i , v j ) min\ d(v_{i}, v_{j})min d(vi,vj)，将v j v_{j}vj加入G p G_{p}Gp中；
- 以v j v_{j}vj为转节点，查询是否有“v i v_{i}vi出发，经过v j v_{j}vj到∀ v k ∈ G − G p \forall v_{k}\in G-G_{p}∀vk∈G−Gp的更短路径”，有则更新表l i s t 1 list1list1中的距离d ( v i , v k ) d(v_{i}, v_{k})d(vi,vk)；
- 对于2中新得到的G p G_{p}Gp重复执行2~4，不断更新l i s t 1 list1list1和G p G_{p}Gp直至G p = G G_{p}=GGp=G为止。
算法例子
与Prim的异同
容易看出此处G p G_{p}Gp和G − G p G-G_{p}G−Gp其实就是Prim算法(描述1)中的集合A AA和集合B BB。
区别在于，Prim算法中更新A AA时，考虑的是∀ v h ∈ A \forall v_{h} \in A∀vh∈A到∀ v j ∈ B \forall v_{j} \in B∀vj∈B的最短距离d h , j d_{h,j}dh,j；而Dijkstra算法中，我们不关心节点到联通分量G p G_{p}Gp的距离，而是要溯源于v i v_{i}vi——因此，考虑v i v_{i}vi到∀ v j ∈ G − G p \forall v_{j} \in G-G_{p}∀vj∈G−Gp的距离d i j d_{ij}dij。
因此，显然Dijkstra算法得到的子图，也是一颗生成树。只不过由于算法机制，得到的不一定是最小生成树。但这棵树满足"根节点到任意叶子节点的距离是全局最小的"这一要求。