数据结构和算法-图的基本操作以图的广度优先遍历和深度优先遍历

2023-12-14 12:44:40

文章目录

图的基本操作

总览

在这里插入图片描述

找边

邻接矩阵直接找图中的某个元素是否为1即可
邻接表要遍历顶点的边链表
在这里插入图片描述
在这里插入图片描述

列出与某顶点相连的边

邻接矩阵找行或列
邻接表找顶点对应的边链表
对于有向图的邻接表的入边时候需要将其他顶点的边链表都遍历
在这里插入图片描述
在这里插入图片描述

插入顶点

此时插入的是与其他顶点都没有连接的顶点
在这里插入图片描述

删除顶点

邻接矩阵设置 顶点中的一个变量为布尔型变量用来标记该顶点是否有效，当删除该节点时，只需将该节点所在行和列设置为0即可
邻接表即遍历所有边链表，将有顶点的边都删除，并修改对于的边链表
在这里插入图片描述
在这里插入图片描述

增加边

在这里插入图片描述

顶点的第一个邻接点

就是遍历到的第一个
在这里插入图片描述
在这里插入图片描述

顶点的下一个邻接点

就是遍历到的第二个
在这里插入图片描述

设置或者获取某条边的权值

在这里插入图片描述

总览

在这里插入图片描述

图的广度优先遍历

总览

在这里插入图片描述

树的广度优先遍历

即找根节点的孩子节点先
在这里插入图片描述

图的广度优先遍历

即先访问节点的相邻节点
在这里插入图片描述

树vs图

图遍历可能访问到原先的节点，但树不会，因为它是一直访问孩子节点的
在这里插入图片描述

在这里插入图片描述

图广度优先遍历的代码实现

在这里插入图片描述
访问后入队，然后出队后再将其相邻且没有访问的节点访问，然后再入队，然后再出队再将其相邻且没有访问的节点访问，如此反复
在这里插入图片描述

广度优先遍历序列

在这里插入图片描述

遍历序列的可变性

不同邻接表对应的遍历序列可能不一样
在这里插入图片描述

算法存在问题

非连通图无法遍历完所有节点
解决方法就是每个节点都广度优先遍历
下面是改进

在这里插入图片描述

改进后的 复杂度分析

从结点树和边数考虑（从访问顶点和找各条边考虑）
在这里插入图片描述
在这里插入图片描述

广度优先生成树

广度优先遍历过程生成的
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

广度优先生成森林

即对各个连通分量广度优先遍历即可
在这里插入图片描述

练习：有向图的BFS

有些点BFS不能遍历完所有的结点
在这里插入图片描述

小结

在这里插入图片描述

图的深度优先遍历

总览

在这里插入图片描述

树的深度优先遍历

在这里插入图片描述

图的深度优先遍历

在这里插入图片描述

算法存在的问题

依然是所有顶点都深度优先遍历一次
在这里插入图片描述

复杂度分析

即可能同时调用V次代码（或者说来自递归工作栈）
在这里插入图片描述
即每个结点最终都会进入一次深度优先遍历函数，这样才可能最终深度优先遍历所有节点
只不过邻接矩阵中对应节点进入函数后时间复杂度为V
而邻接表为E
在这里插入图片描述

深度优先遍历序列

在这里插入图片描述
邻接表不一样，深度优先遍历序列可能不一样
在这里插入图片描述
在这里插入图片描述

深度优先生成树

同样，即将遍历序列的其他边去了即可
在这里插入图片描述

深度优先生成森林

在这里插入图片描述
在这里插入图片描述

图的遍历与图的连通性

在这里插入图片描述
在这里插入图片描述

小结

在这里插入图片描述

文章来源:https://blog.csdn.net/llovewuzhengzi/article/details/134936769
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。