数据结构(6):图

1 图的基本概念

1.1 基本概念

1.1.1 定义【多对多的关系】

一个图不可能是空图！！！一个图的顶点集一定是非空集，但是边集可以为空集！

1.1.2 应用

1.2 无向图和有向图

弧头是有箭头的那一边，弧尾是没有箭头的那一边！！！

1.3 简单图和多重图

怎末判断是不是社交达人是不是大V？所以研究顶点有多少的相连的边是很有意义的一件事情！

1.4 顶点的度、入度、出度

入度和出度之和！！！

在无向图中：

度之和等于边个数的两倍！！！

在有向图中：

出度和入度是相等的！

1.5 顶点与顶点的关系描述

顶点和顶点之间可能不存在路径！

不重复出现是简单！

强联通！

连通图、强连通图！！

无向图不用形成回路就可以连通  但是有向图只有形成回路才是强联通了！！！

1.6 子图

生成子图！：有所有的顶点但是可能少拿的几个边！！

1.7 连通分量！！！

极大 连通 子图！

1.8 强连通子图

形成回路！！！

1.9 生成树！！【连通图】

顶点是n的树，一定有n-1条边，砍掉一条边则不连通，加上一个边必然形成回路！！！

树是：没有回路但是连通的无向图！！！！

1.10 生成森林【非连通图】

连通分量的生成树构成了生成森林！

1.11 边的权、带权图/网

带权路径之和！

1.2 几种特殊形态的图

完全

任何两个顶点都存在边！--完全

稀疏、稠密

树、有向树

有向树不连通哦！有一个顶点入度为0说明谁都达到不了哦！那肯定不连通咯

总结

2  图的存储及基本操作

2.1 邻接矩阵法

有边则对应位置为1

用二维数组存放【0，1】和一个一维数组存放顶点！

一维数组存放的顶点 对应的坐标就是矩阵的第几列！

入度出度

时间复杂度

是o(|v|) 其中|v|表示的是顶点的个数！

带权图

定义无穷时：可用int的上限定义无穷大！

有时把自己指向自己的权值记为0，也就是说当值为0或无穷是 就是没有自己指向自己的边！

空间复杂度

无向图的邻接矩阵是对称矩阵可以使用压缩存储的方法！！！

详情可见：数据结构(3)栈、队列、数组-CSDN博客

矩阵的性质：相乘

B-B 长度为2的路径一共有3条！

总结

2.2 邻接表法

用一维数组存放顶点的信息 指向顶点的第一条边！

和树的孩子表示法是一样的，指向第一个孩纸！！

先创建结点，然后初始化   【//“结点”---//用邻接表存储的图】！

时间复杂度

入度、出度

度：无向图是很简单的，只需要遍历对应的顶点后边连了几个就行

[超大缺点！！！]

入度：这个比较麻烦，所有顶点的边列表遍历一遍然后计算出所求顶点的入度!

出度：也是和无向图一样

邻接表不唯一，但是邻接矩阵一定唯一！！！！

总结

2.3 十字链表【有向图】

解决了找顶点不方便和计算入度不方便的问题！！

十字链表的画法

时间复杂度

顺着橙色的就可以找到入度，只需要顺着橙色这找卡看有几个；同理出度顺着绿色的找！！

从绿色出发找到出度：

最后一个指向null

从橙色出发找到入度：

其实整体画出来之后可以看出来，绿色数字代表画在了第几行，橙色数字代表画在了第几列，每一个方块表示的是：从绿色到橙色有一条边！

2.4 邻接多重表存储【只 无向图】

每个边对应两分冗余的数据，那么处理起来解很麻烦！

上边的数组的含义就是橙色指向绿色的边！！！

B存在在那个颜色就顺着那个颜色往后找！

边结点只有一个 删除起来就比较简单！

空间复杂度

存储方式大全总结

2.5 图的基本操作

邻接矩阵和邻接表是比较重要的，那两个太复杂考研不考！

遍历所有的边结点！E是一共有多少个边边

只需修改一行和一列的数据，然后在定义的时候给出顶点是空顶点的bool变量即可，这样可以避免大量的数据移动！！！

邻接表 删除的结点有两部分哦！！！

这个是无向图，就是说结点是冗余出现的，因此只需要 遍历与之链接的边结点 找到对应重复的哪一个边结点然后删除就好了

邻接表添加元素可以使用尾插法和头插法，省时间的是头插法！（o(1)）（不用遍历！）

出边是行、入边是列！

基本操作总结

黄色的两个算法经常在图的遍历算法中使用到！

直接调用函数接口也是可以的！

3 图的遍历

3.1 图的广度优先遍历BFS

树是特殊的图！

1 234 5678横向的找

2 16 537 48

树vs图

通过一个结点找到相邻的其它结点

树实现：找孩子

图：有回路可能重复访问同一个元素！

无向图的代码实现

所以那个for循环一直到 -- 下一个没有了，返回的是-1时！！

遍历序列的可变性

邻接矩阵的表示方式一定唯一，是递增的顺序排列的！

但是邻接表就不一定了哦！

算法存在的问题：非连通图可能没遍历完，进一步完善！

复杂度分析

空间复杂度：

主要来源于辅助队列！！！[不是那个标记数组！！！]就是入队出队那个进行广度优先遍历的那个！！

时间复杂度：

主要来源访问各个顶点以及探索各条边

邻接矩阵不知道那个位置是1所以要全部遍历 则是v*v

邻接表后边的就是相连的！！，所以访问 所有的顶点的预期相连的边 在无向图中 后面一共有2E条；在有向图中 一共有E个！

不要钻到代码里！的循环里 容易乱哦！

广度优先生成树

根据广度优先的顺序生成的

当邻接表的表示方式改变时，过度优先生成树可能不同

广度优先生成森林

有向图BFS代码实现

3.2 图的深度优先遍历DFS

树的深度优先遍历

图的深度优先遍历

递归函数的调用过程要用栈！进行辅助理解！

DFS代码实现：

空间复杂度

时间复杂度

深度优先手写

邻接表不一样的话结果可能也不一样

深度优先生成树

把写出深度优先序列的经过的边标红 最后没有标红的不要 然后展开！

深度优先生成森林

连通分量大于1的时候就可以生成森林了

3.3 图的遍历的图的连通性

4 图的应用

4.1 最小生成树

4.1.1 最小生成树的概念

边是n-1个这才是极小连通子图！

最小生成树题目描述

简单试一下

最小生成树概念

最小生成树可能有多个！

4.1.2 Prim算法【不要求代码！】

怎么确定是哪个顶点呢？从那个顶点好像都一样

 实现的代码思想：

没加入顶点之后 都更新lowCost数列！【检查没有加入的顶点是否和新加入的顶带你有边如果有的话，是否比原来的要小，小的话就更新数列中的值！】

时间复杂度

每一轮的处理中都需要进行两次的循环遍历，一次给isjoin，一次给lowcost；所以合起来是2n

4.1.3 Kruskal算法(克鲁斯卡尔)

找一个最小的边

实现的思想：

初始：将各条边按照权值排序

看两个顶点是否相连用到了并查集的概念！

4.1.4 Prim算法v.s. Kruskal算法

总结：

4.2 最短路径问题

常见的两种问题类型：

4.2.1 BFS算法【广度优先算法】

只适用于无权图！

d[]存储距离

path[]存储前驱结点

vistied[]表示是否被访问过

过程：

1、把初始路径长度d[]记为无穷 path[]的值置为-1

2、将出发顶点的d[]置为0

3、访问下一个顶点并作以下操作：路径长度+1；path[]更新；visited[]更新

4、弹出队列中的下一个顶点重复 visitied的过程！

最后得到两个数组：

使用：

与广度优先生成树的关系

4.2.2 Dijkstra算法

BFS的局限性

Dijkstra算法【有向或者无向图】（不要求代码）

第一轮循环：

先找到和v0直接相连中路径最短的边 纳入

然后从这个顶点出发检查路径的大小【全部】是否优于原来的 如果优于就更新

第二轮：

【从谁开始更新谁的final值就设为true】

看更新之后的dist 找到最小的那个对应的顶点 从这个出发进行新一轮的更新！

更新只需要更新Final[]值为false的！

使用数组信息

反着找！

代码【不要求】

时间复杂度

每一次都需要把dist扫一遍 长度是V

一共弄了V-1遍

所以时间复杂度是O(v^2)

对比prim算法

小坑：有负的权值的话，可能找不到最短的路径

对于v2就是不对的

4.2.3 Floyd算法

动态规划思想！

算法实现过程：

两个矩阵：是横坐标表示的到纵坐标表示的有向图！

然后一个一个顶点当中转点，知道没有点了

初始：

在v0中转

允许在v1中转

允许在v2中转

怎末看表

代码实现

时间复杂度和空间复杂度

看个更复杂的

当没有中转点时，即path[]=-1时说明两个之间没有东西，顶点才写完！

写完红色的检查 两次0-3 有无中转 【即检查path[0][3] = -1则无中转否则就是有 有的话把那个顶点加进来，两两之间再进行检查看是不是直接到达！一直到写出完整的路径信息】

path矩阵递归地找到完整路径！【代码不要求 他也没说！】

Floyd算法可以用于负权图

但也有局限性：不能解决带有“负权回路”的图

因为转的圈数越多，代价就会变得越小，所以求不出来就不存在最短路径

4.2.4 三个算法总结

BFS两个时间复杂度：v^2 是当存储方式是邻接矩阵时；另一个是狼存储方式是邻接表时

4.3 有向无环图描述表达式【没有环路！】

算数表达式可以用树存储，但会重复

干掉一个树，节省存储空间

再干掉一个

两个b还能合并 最后就变成了

很乱的过程但是有真题

真题

应该选A

写出有向无环图的 不会漏方法

不会出现重复的操作数！

操作符肯定不能重复

下面一层一层的检查 运算符是否能合并【只有当左右  相连的东西 都一样的时候才可以合并！】

练习：

但是当运算符的优先顺序进行调整的话，发现最后的结果不一样，说明得到的结果可能不唯一！！！

4.4 拓扑排序

必须式DAG图，即有向无环图！

AOV网

活动有先后顺序！ 一定是有向无环图！

如果有环路的话 没完了 

拓扑排序

为了找到做事的先后顺序

拓扑排序序列的结果不唯一！

实现步骤

代码实现：

有无回路看count！

代码少了声明了两个数组：indegree[]和print[]

初始化 第一次循环

count是一个指针的作用用于记录弹出的是谁 存储再print数组中

count++先用count的值 然后再对count的值进行+1的操作！

弹出的那个顶点会从有向无环图（DAG）中删除，那么与其相连的顶带度会-1

最后当count的值是顶点的个数的时候 说明拓扑排序成果；如果不是说明有回路，拓扑排序失败！

时间复杂度

逆拓扑排序：

删除一个顶点，就要删除指向这个顶点的边：

如果采取邻接表 每次都要从头遍历！邻接矩阵只需要遍历他所在的那一列就行！

也可以采取逆存储邻接表

逆拓扑排序的DFS实现

DFS就是按照深度优先遍历的原则 将顶点一个一个压入栈中 后继无人的时候一个个弹出 直到栈为空 栈为空时检查vistied[]标记序列是否都为TRUE 如有FALSE说明还有顶点没有访问过，从这个顶点出发再次DFS 直到后继无人然后弹出栈 

如果有回路怎么办！！！！？？？怎末识别出来回路

如果下一个顶点是已经true的那一定有回路了 一个顶点灰了两次还得了!

总结

因此拓扑排序也适用于判断一个图里有没有环！！

4.5 关键路径

AOE网

用边表示活动！而AOV是用顶点表示活动!

AOE网的性质：

只有一个源点和汇点！

源点到汇点--就是路径 最大路径长度是关键路径！

最早时间！

最早 从前往后推，最晚从后向前推！

求所有事件的最早发生时间：

【有两条路的话就选最大的】

有拓扑排序 开始的点是0 接着往下找就可以可

拓扑序列得到可以通过DFS深度优先得到【做事的先后顺序构成了拓扑序列】

所有时间的最迟发生时间

有两条路的话就选最小的

所有活动的最早发生时间

弧尾 连接的时间的最早发生时间就是活动的最早发生时间！

所有活动的最迟发生时间

基于弧头时间的最晚发生时间 - 这个活动所需的时间就行！

所有活动的时间余量

最晚-最早   这样就可以得到那些活动一定不能拖延！

关键活动、关键路径的特性

总结！！！