数据结构-图 _

图是一种较为复杂的非线性结构。为啥说其较为复杂呢根据前面的内容我们知道线性数据结构的元素满足唯一的线性关系每个元素(除第一个和最后一个外)只有一个直接前趋和一个直接后继。树形数据结构的元素之间有着明显的层次关系。但是图形结构的元素之间的关系是任意的。何为图呢简单来说图就是由顶点的有穷非空集合和顶点之间的边组成的集合。通常表示为G(V,E)其中G 表示一个图V 表示顶点的集合E 表示边的集合。下图所展示的就是图这种数据结构​编辑同时图⼜分为有向图与⽆向图上⾯的是⽆向图因为边没有指明⽅向只是表示两者关联关系⽽有向图则是这样​编辑图在我们日常生活中的例子很多比如我们在社交软件上好友关系就可以用图来表示。图的基本概念顶点图中的数据元素我们称之为顶点图至少有一个顶点非空有穷集合对应到好友关系图每一个用户就代表一个顶点。边顶点之间的关系用边表示。对应到好友关系图两个用户是好友的话那两者之间就存在一条边。度度表示一个顶点包含多少条边在有向图中还分为出度和入度出度表示从该顶点出去的边的条数入度表示进入该顶点的边的条数。对应到好友关系图度就代表了某个人的好友数量。无向图和有向图边表示的是顶点之间的关系有的关系是双向的比如同学关系A 是 B 的同学那么 B 也肯定是 A 的同学那么在表示 A 和 B 的关系时就不用关注方向用不带箭头的边表示这样的图就是无向图。有的关系是有方向的比如父子关系师生关系微博的关注关系A 是 B 的爸爸但 B 肯定不是 A 的爸爸A 关注 BB 不一定关注 A。在这种情况下我们就用带箭头的边表示二者的关系这样的图就是有向图。无权图和带权图对于一个关系如果我们只关心关系的有无而不关心关系有多强那么就可以用无权图表示二者的关系。对于一个关系如果我们既关心关系的有无也关心关系的强度比如描述地图上两个城市的关系需要用到距离那么就用带权图来表示带权图中的每一条边一个数值表示权值代表关系的强度。下图就是一个带权有向图。​编辑图的存储邻接矩阵存储邻接矩阵将图用二维矩阵存储是一种较为直观的表示方式。如果第 i 个顶点和第 j 个顶点之间有关系且关系权值为 n则A[i][j]n。在无向图中我们只关心关系的有无所以当顶点 i 和顶点 j 有关系时A[i][j]1当顶点 i 和顶点 j 没有关系时A[i][j]0。如下图所示​编辑值得注意的是无向图的邻接矩阵是一个对称矩阵因为在无向图中顶点 i 和顶点 j 有关系则顶点 j 和顶点 i 必有关系。​编辑邻接矩阵存储的方式优点是简单直接直接使用一个二维数组即可并且在获取两个定点之间的关系的时候也非常高效直接获取指定位置的数组元素的值即可。但是这种存储方式的缺点也比较明显那就是比较浪费空间邻接表存储针对上面邻接矩阵比较浪费内存空间的问题诞生了图的另外一种存储方法—邻接表。邻接链表使用一个链表来存储某个顶点的所有后继相邻顶点。对于图中每个顶点 Vi把所有邻接于 Vi 的顶点 Vj 链成一个单链表这个单链表称为顶点 Vi 的邻接表。如下图所示​编辑​编辑大家可以数一数邻接表中所存储的元素的个数以及图中边的条数你会发现在无向图中邻接表元素个数等于边的条数的两倍如左图所示的无向图中边的条数为 7邻接表存储的元素个数为 14。在有向图中邻接表元素个数等于边的条数如右图所示的有向图中边的条数为 8邻接表存储的元素个数为 8。图的搜索图⾥⾯遍历⼀般分为⼴度优先遍历和深度优先遍历⼴度优先遍历是指优先遍历与当前顶点直接相关的顶点⼀般借助队列实现。⽽深度优先遍历则是往⼀个⽅向⼀直⾛到不能再⾛有点不撞南墙不回头的意思⼀般使⽤递归实现。广度优先搜索广度优先搜索就像水面上的波纹一样一层一层向外扩展如下图所示​编辑广度优先搜索的具体实现方式用到了之前所学过的线性数据结构——队列。具体过程如下图所示第 1 步​编辑第 2 步​编辑第 3 步​编辑第 4 步​编辑第 5 步​编辑第 6 步​编辑深度优先搜索深度优先搜索就是“一条路走到黑”从源顶点开始一直走到没有后继节点才回溯到上一顶点然后继续“一条路走到黑”如下图所示​编辑和广度优先搜索类似深度优先搜索的具体实现用到了另一种线性数据结构——栈。具体过程如下图所示第 1 步​编辑第 2 步