|
图：由定点和边组成。分为无向图和有向图。
主要实现方法有：
查询边的数量。
查询顶点的数量。
添加顶点。
添加无权边。
添加有权边。
删除顶点。
删除边。
广度优先搜索bfs：借助队列，类似二叉树的层序遍历。
深度优先搜索dfs：借助栈，类似二叉树的前序遍历。
拓扑排序：借助队列，不断找到入度为0的顶点。
最小生成树，针对无向图。
最小生成树，有V个顶点，V-1条边。
具体算法有：
①prim算法：从一个顶点开始，这个顶点所有的边中最小权值的那条边(借助最小堆)是构成最小生成树的边，依次类推。直到找到V-1条边。
②kruskal算法：将所有的边的权值按从小到大排序（借助最小堆），从中找到V-1条边，就是构成最小生成树的边。注意找到的边数从第3条开始，可能构成环，可以借助并查集来判断这条边的from和to是否在同个集合中，如果在，则会构成环，舍弃该边。如果不在，则将该边的from和to加到同个集合中。(在生成最小生成树之前，需要初始化各个顶点属于各自的集合)
求图的最短路径的方法：
①Dijkstra算法
属于单源最短路径算法，即从一个顶点出发，不断的选择权值最小的路径，并对边进行松弛操作。其中松弛操作就是更新源点到另一个顶点的最短路径值。可以类比将各个顶点当成石头，各个边当成绳子，然后从某个石头出发，拽起这个石头，最终全部石头离开地面，各个绷直的绳子的长度就是从出发顶点到各个顶点的最短路径。不支持负权边，负权环。
②Bellman-Ford算法
属于单源最短路径算法，对所有边进行V-1次松弛操作（V是节点的数量），得到所有可能的最短路径。支持负权边，还能检测是否存在负权环。
③Floyd算法
属于多源最短路径算法，能够求出任意两个顶点之间的最短路径，支持负权边。时间复杂度是O（V3次方）要比执行V次Dijkstra算法的效率要好，V是顶点的数量。
从任意顶点i到j的最短路径有两种：
1.直接i到j
2.i经过若干顶点到j
3层循环，比较i但j的距离与i到k和k到j的距离大小。
|