概念

完全图:任何两个节点之间都有边。
连通图:任何两个节点之间都有路径。

数据结构 描述 优点
邻接矩阵法 用一个数组存顶点,用一个矩阵存边 直观
邻接表法 用一个数组存顶点,每个顶点维护一个它指向的节点链表 找节点出去的边容易
逆邻接表法 用一个数组存顶点,每个顶点维护一个指向它的节点的链表 找节点进入的边容易
十字链表法 结合邻接表与逆邻接表,相当两套链表用同样的节点 找节点出边和入边都容易
邻接多重表法 每个顶点都维护一个与它相邻的边的链表,边节点是各顶点共用的 存无向图,易于对边操作

图搜索算法

深度优先搜索:节点优先级=父节点优先级-1,越深的节点优先级越小,越优先。
广度优先搜索:节点优先级=父节点优先级+1,越深的节点优先级越大,浅节点比深节点优先。

最短路径

最短路径-Dijkstra算法:优先探索累积权值最小的那条路径,这是贪心算法,结果并不一定是全局最优的。
最短路径-Floyd算法:

image

第一次迭代,所有节点绕行1号节点。
第二次迭代,所有节点绕行2号节点。
...
第n次迭代,所有节点绕行n号节点。

最终会得到所有节点到所有节点的最小路径。

最小生成树

最小生成树-Prim算法:非常类似于Dijkstra算法,总是获取离定点最近的那个点。
最小生成树-Kruskal算法:最小生成树的各边权值之和最小,所以搜索时总是朝着权值最小的边扩展生成树。

拓扑排序

①每个定点出现且只出现一次
②若A定点排在B的前面,则在图中不存在B到A的路径。

关键路径

①只有在某定点所代表的事件发生后,从该定点出发的各有向边所代表的活动才能开始;
②只有在进入某定点的各有向边所代表的活动都已结束时,该定点所代表的事件才能发生。

posted @ 2021-09-26 19:56:33
评论加载中...

发表评论