Go 小白理念6.1_1_图
6.1_1_图的基本概念
图
应用场景：比如社交网络中用户之间的关系，网络设备之间的拓扑结构，以及显示生活中形形色色的网：公路网、铁路网、地铁网等等，都可以通过图来表示。
图的存储
邻接矩阵
对于有 n 个顶点的图而言，时间复杂度是 O(n^2)，空间复杂度也是如此，而且如果图比较稀疏的话（稀疏图），边数组会存在巨大的空间浪费。但是优点是实现起来非常简单，对于稠密图或者非常简单的图来说，用邻接矩阵是比较方便的。
邻接表
邻接表的构建时间复杂度要比邻接矩阵好，对于一个有 n 个顶点和 e 条边的图而言，时间复杂度是 O(n+e)，而且不存在任何空间的浪费，比较高效，可用于存储任何图。
图的遍历
深度优先搜索（DFS）
广度优先搜索（BFS）
广度优先搜索的时间复杂度和深度优先搜索一样，也是 O(v+e)，其中 v 表示顶点数，e 表示边数，需要额外的数组存储已访问顶点和前驱顶点，对应的空间复杂度是 O(v)。
广度优先搜索和深度优先搜索的复杂度完全一样，没有优劣之分，具体使用哪种搜索方式，以实际情况为准。
最小生成树
应用场景：规划路径让交通费用最低，国家的电力网、公路网、通信网，规划路径让建设成本最低，计算出最佳路径，连接网络中所有节点的最优路径问题，都可以通过最小生成树来处理。
普里姆算法（Prim）
最小生成树 prim 算法采用了贪心策略
克鲁斯卡尔算法（Kruskal）
组成环则丢弃
直到选择了 N-1 条边即完成
最短路径
迪杰斯特拉算法（Dijkstra）
贪心策略
和 prim 算法很类似，Dijkstra 计算距离是累加
弗洛伊德算法（Floyd）
动态规化思想
prim，kruskal 和 dijkstra 算法有贪心策略
- prim：每次执行都选择轻边
- kruskal：每次执行都选择权值最小的边，同时合并两个不相交的子集
- dijkstra：每次执行都选择路径最短 d (s,t)，并将顶点 t 加入到集合 S 中，同时对边进行松弛
拓扑排序（AOV 网）
应用
关键路径
关于 LearnKu
粤公网安备 44030502004330号