看Prim算法之前要先知道什么是最小生成树。
对于一个如下的图，求最小生成树的权值。
首先定义一个数组map[N][N]（N根据题目决定大小）存放权值。对其进行初始化：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
| 0 | – | – | – | – | – | – | – |
| 1 | – | ∞ | 5 | 8 | ∞ | ∞ | ∞ |
| 2 | – | 5 | ∞ | ∞ | 6 | 8 | ∞ |
| 3 | – | 8 | ∞ | ∞ | ∞ | 1 | ∞ |
| 4 | – | ∞ | 6 | ∞ | ∞ | 3 | 5 |
| 5 | – | ∞ | 8 | 1 | 3 | ∞ | 6 |
| 6 | – | ∞ | ∞ | ∞ | 5 | 6 | ∞ |
标签存档: 最小生成树
最小生成树Prim算法
作者: admin
日期: 2012 年 3 月 12 日
没有评论
近期评论