数据结构 | 第七章图

怼烎@ 2021-11-27 06:20 423阅读 0赞

很具体的知识点参考大佬blog：  
[https://blog.csdn.net/yuanlaijike/article/details/78074765][https_blog.csdn.net_yuanlaijike_article_details_78074765]  
[https://blog.csdn.net/qq\_36673275/article/details/79595852][https_blog.csdn.net_qq_36673275_article_details_79595852]

以下是自己未知/易错的知识点:

--------------------

*  有向图的度数是出度+入度，都是正整数，出度不是负数
 *  无向图中的极大连通子图称为该无向图的连通分量，只要连通就行，不用管有没有环。
 *  在有向图 G=（V，\{A\}）中，若对于每对顶点 vi、vj∈V 且 vi≠vj，从 vi 到 vj和 vj到 vi都有路径，则称该有向图为强连通图。有向图的极大强连通子图称做有向图的强连通分量。
 *  显然，强连通图只有一个强连通分量，即本身，非强连通图有多个强连通分量。
 *  连通图G的生成树，是G的包含其全部n个顶占的一个极小连通子图,它必定包含且仅包含G的n-1条边。
 *  十字链表：[https://blog.csdn.net/qilimi1053620912/article/details/89522246][https_blog.csdn.net_qilimi1053620912_article_details_89522246]

**图的遍历**

*  深度优先搜索  
    代码实现
 *  广度优先搜索

**最小生成树**

*  普里姆算法：以点为依靠找代价最小的边
 *  克鲁斯卡尔算法：直接找代价最小的边形成环就舍弃

**最短路径**

*  迪杰斯特拉算法  
    （1）把图中顶点集合分成两组，第一组为集合S，存放已求出其最短路径的顶点，第二组为尚未确定最短路径的顶点集合是V-S(令W=V-S)，其中V为网中所有顶点集合。  
    （2）按最短路径长度递增的顺序逐个把W中的顶点加到S中，直到S中包含全部顶点，而W为空。  
    （3）在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到W中任何顶点的最短路径长度。  
    （4）此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，W中的顶点的距离从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。
 *  弗洛伊德算法  
    （1）从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。 　　  
    （2）对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。

**有向无环图及其应用**

*  拓扑排序  
    给出有向图G=(V,E)，对于V中的顶点的线性序列(vi1,vi2,…,vin)，如果满足如下条件：若在G中从顶点 vi到vj有一条路经，则在序列中顶点vi必在顶点 vj之前；则称该序列为 G的一个拓扑序列(Topological order)。

构造有向图的一个拓扑序列的过程称为拓扑排序(Topological sort)。

拓扑排序实现步骤如下：

（1）从AOV网中选一个入度为0的顶点v且输出之；

（2）从AOV网中删除此顶点v及所有出边；

（3）重复（1）、（2）两步，直到AOV网中不存在无前驱的顶点为止。

*  关键路径  
    把从源点到汇点的最长路径称为关键路径，关键路径上的活动称为关键活动。

[https_blog.csdn.net_yuanlaijike_article_details_78074765]: https://blog.csdn.net/yuanlaijike/article/details/78074765
[https_blog.csdn.net_qq_36673275_article_details_79595852]: https://blog.csdn.net/qq_36673275/article/details/79595852
[https_blog.csdn.net_qilimi1053620912_article_details_89522246]: https://blog.csdn.net/qilimi1053620912/article/details/89522246