数据结构和算法-图的基本概念及邻接矩阵法和邻接表法和十字链表法和链表链表法

2023-12-15 11:33:02

文章目录

图的概念

总览

在这里插入图片描述

图的定义

顶点不能为空，边可以为空，且边对于两端必须要有顶点
在这里插入图片描述

图逻辑结构的应用

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

无向图和有向图

在这里插入图片描述

简单图和多重图

在这里插入图片描述

顶点的度，入读，出度

无向图中一条边对应两个节点产生两个度
有向图中一条边对应两个节点，一个节点产生入读，另一个节点产生出度
在这里插入图片描述

顶点-顶点的关系描述

连通（无向图中）：两个顶点有路径存在
强连通（有向图中）：两个顶点有来回路径
在这里插入图片描述

连通图，强连通图

对于n个顶点的无向图G
若要为连通图，则保证n个顶点连成一条线即可，那么有n-1条边
若要为非连通图，则将一个顶点隔离，将剩余的节点的边连满，相当于是计算从n-1个顶点中选两个顶点的种类数有多少，此时连满后再增加任意条边，只能是隔离的那个顶点连接到剩余的节点上，此时将连通，所以不行。所以只需计算将剩余的节点的边连满的边数

对于n个顶点的有向图
若要为强连通图，则最少有n条边（即形成回路，此时任意一个顶点沿回路方向出发都能到达任何一个顶点）
在这里插入图片描述

研究图的局部-子图

无向图和有向图对于子图相关的概念差不多
子图也是一个图，所以也要符合图的要求

无向图

在这里插入图片描述

有向图

在这里插入图片描述

连通分量

在这里插入图片描述

强连通分量

在这里插入图片描述

生成树

在这里插入图片描述

生成森林

在这里插入图片描述

边的权，带权图/网

在这里插入图片描述

几种特殊形态的图

在这里插入图片描述
在这里插入图片描述
有向树不是强连通的
在这里插入图片描述

小结

在这里插入图片描述

邻接矩阵

总览

在这里插入图片描述

邻接矩阵

就是横坐标和纵坐标都为点的图，相连为1，不相连为0
领结的意思就是是否相邻连接
在这里插入图片描述

在这里插入图片描述

求顶点的度，入度，出度

无向图对应左边，有向图对应右边

在这里插入图片描述

邻接矩阵存储带权图

在这里插入图片描述

性能分析

在这里插入图片描述

在这里插入图片描述

邻接矩阵法的性质

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

小结

在这里插入图片描述

邻接表

在这里插入图片描述

顺序+链式存储

用一维数组存图，每个顶点有对应边的指针相关信息
在这里插入图片描述

对比 树的孩子表示法

在这里插入图片描述

有向图vs无向图

同一条边无向图需要存储两次，而有向图只需存储一次，所以空间复杂度有所不同
在这里插入图片描述

求顶点的度，入度，出度

无向图的度：只需遍历该节点对应的边链表
有向图的出度：只需遍历该节点对应的边链表
有向图的入度：需要遍历该节点之外的所有节点的边链表（麻烦）
有向图的度：即入度+出度

表示方式不唯一

即点的边链表不唯一
但图的邻接矩阵唯一
在这里插入图片描述

小结

在这里插入图片描述

十字链表

总览

在这里插入图片描述

前提问题

邻接矩阵存储空间复杂度高
而邻接表找入边不方便
在这里插入图片描述

十字链表存储有向图

就是存储节点分别为弧的弧尾顶点和弧的弧头顶点的边链表
在这里插入图片描述

性能分析

在这里插入图片描述

邻接矩阵，邻接表存储无向图的缺点

在这里插入图片描述

邻接多重表存储无向图

即一条边只有一个边元素对应，链表表示与某个顶点相连的边
在这里插入图片描述
删除边时，只需要修改前一个的指针为后一个边的指针即可
删除点时,即将该点对应的边链表删除即可，同时修改指向该链表中元素的其他链表的元素指针
在这里插入图片描述

小结

在这里插入图片描述

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