Download presentation
Presentation is loading. Please wait.
1
使用矩阵表示 最小生成树算法
2
无权图的邻接矩阵
3
有权图的矩阵表示 有权图： G = (E , V , w) 矩阵表示： 将原先邻接矩阵中的0,1替换成边的权
其中w为E -> eVal 的一个映射 没有明确看到权是否一定为正
4
矩阵表示Kruskal算法 Edge : v1, v2, weight Graph : V, E, edges 对边进行排序
选剩下的边中最小的，如果形成环就放弃，不形成环就留下 重复第二步，直到有V-1条边 V为顶点数量，E为边的数量，edges为边 如果两个点都已经connected，在两者中间再加一条边必定形成环
5
矩阵表示Kruskal算法 BD = 7 BF = 8 DF = 9 CF = 12 AB = 12 BE = 13 对称性
6
矩阵表示Prim算法 Edge : v1, v2, weight Graph : V, E, edges 选择一个起点
删掉这一列，记录顺序，添加新的被连接的点 选最小 重复，直到有V-1条边 V为顶点数量，E为边的数量，edges为边
7
矩阵表示Prim算法 AF = 9 BF = 14 AC = 20 AE = 25 DE = 26 由于对称性，只需要考虑左下的边。
已经作为起点或者被连接到的点一定是作为起点而不是终点，所以划掉一行（实现的时候记录该点是否connected，若是则跳过）。
8
Thanks! You can find me at: QQ:
Similar presentations
