2019年王道数据结构学习笔记----图

• 最小生成树算法

普里姆算法prim

普里姆算法是不断选点，而选点的依据，在当前点集合向外发出的边的最小值，
另外每次选中一个节点之后更新，已经选中的节点到未被选中节点的距离（这一点也是和求最短路径）

克鲁斯卡算法kruskal

克鲁斯卡算法的核心是不断选边
选边的依据是，在已经排好序的边中选择最短的边，但不能形成环路

• 最短路径算法

  • 迪杰特斯拉

    计算单源点，到各个顶点的距离最短值，
    类似于prim算法，逐个加点，用贪心算法
    从单源点出发，知道到一个最短距离的点，再去更新改源点到其他顶点数据
    更新的依据是，源点直接到其他点距离和源点经过刚刚选中的点，再到其他点之和距离大小关系，若后者小则更新

• Prim算法和Dijkstra算法的异同

都是加点法
区别是更新的算法不一样，
prim算法是通过比较加入点到其他点距离，和源点到其他点距离，小则更新。
迪杰特斯拉算法则是通过比较源点到其他点距离和通过源点到中介点（刚刚加入的点）到其他点距离和的大小比较

• 拓扑排序