数据结构速成--图

admin2024-07-05  14

数据结构速成--图,第1张

目录

一、图的基本结构

二、图的存储结构

三、图的遍历

1. 广度优先遍历(BFS)

2. 深度优先遍历(DFS)

3. 总结

四、最小生成树

五、拓扑排序

六、关键路径


一、图的基本结构

数据结构速成--图,第2张

数据结构速成--图,第3张

二、图的存储结构

数据结构速成--图,第4张

数据结构速成--图,第5张

数据结构速成--图,第6张

数据结构速成--图,第7张

数据结构速成--图,第8张

三、图的遍历

1. 广度优先遍历(BFS)

        广度优先搜索类似于二叉树的层序遍历算法。一般用队列实现。

数据结构速成--图,第9张

2. 深度优先遍历(DFS)

         深度优先搜索类似于树的先序遍历。常用来实现。

数据结构速成--图,第10张

3. 总结

        BFS就是一口气把和顶点相连的所有顶点遍历,从遍历结果的第二个顶点继续把和第二个顶点相连的所有未遍历的顶点输出。

        DFS是先遍历和顶点相连的一个顶点,再从这个顶点出发找一个相连的顶点,重读步骤,如果当前顶点和他相连的所有顶点都遍历过了,就看前面的顶点他相连的有没有没遍历的。

        因此我们也可以根据邻接表/邻接矩阵写出BFS或DFS遍历序列。

四、最小生成树

数据结构速成--图,第11张

数据结构速成--图,第12张

数据结构速成--图,第13张

数据结构速成--图,第14张

五、最短路径

        顶点到自身的距离为0,每加入一个最短的路径,就要看该顶点到其他顶点的最短路径有没有发生改变。

数据结构速成--图,第15张

数据结构速成--图,第16张

五、拓扑排序

        拓扑排序可以用来判断是否存在回路/环。

数据结构速成--图,第17张

数据结构速成--图,第18张

六、关键路径

        从开始顶点到结束顶点的所有路径中,具有最大路径长度的路径称为关键路径。

数据结构速成--图,第19张

        关键路径上的所有活动都是关键活动,因此可以加快关键活动来缩短整个工程的工期
        网中的关键路径并不唯一,且对于有几条关键路径的网,只提高一条关键路径上的关键活动并不能缩短整个工程的工期,只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的

数据结构速成--图,第20张

数据结构速成--图,第21张

注意:ve(i)找最大的,vl(i)找最小的。

数据结构速成--图,第22张

        d(i)=0即为关键路径。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!