Graph

图的一些定义

• 图的表示：邻接矩阵(顶点列表Vertex +边矩阵)、邻接表（顶点存在一维数组，所有邻接的节点用线性链表表示）

图的一些应用

• 得到最小生成树[不存在回路的连通图, n个顶点 n-1条边]

Kruskal算法
初始时只有n个顶点，然后使用贪心算法，每次都找权值最小的，如果一旦成环continue。直到选到n-1条边。
Prim算法
依次将距离已在树上的节点最小权值的边加入到路径中，同时将它关联的节点加入到树中

• 最短路径

Dijkstra => 算法单源最短路径[任意两点最短路径]
1.找出源点到各个终点的距离[无法直达为无穷远]
2.在这些距离中找出最短的，加入相应的顶点
3.调整各重点对路径的距离(是否通过新加入的顶点到各终点的距离更短)

Floyd => 算法某点到其他所有点的最短路径
初始：记录权值情况和路径矩阵

然后依次加入每个点试探：

• 是否加入这个定点后原来无穷大变化了。
• 是否加入这个定点后原来权值大的变小了。