数据结构 图

星期六, 8月 3, 2019 | 4分钟阅读 | 更新于 星期二, 3月 14, 2023

@

一、定义

图是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合。图中不允许没有顶点,但是可以没有边

基本术语:

  • 有向边:顶点之间的边有方向,简称弧,箭头的一边为弧头,另一边为弧尾;如果边没有方向则是无向边
  • 有向图:任意两个顶点之间的边均是有向边的图;如果均是无向边就是无向图
  • 完全图:任意两顶点之间都存在边的无向图是无向完全图;任意两顶点之间都存在两条边的有向图是有向完全图
  • 稠密图:一个含有较多边的图;相对的,含有较少边的图时稀疏图
  • 顶点的度:连接该顶点的边的数量;在有向图中,该顶点入边数量是入度,该顶点出边数量是出度
  • 邻接:两个顶点之间有边;有向边的起始顶点称为入边邻接顶点,有向边的结束顶点称为出边邻接顶点
  • 路径:图中首尾相连的一组边;首和尾是同一个顶点的路径称为环
  • 简单路径:不存在环的路径;首和尾是同一个顶点的简单路径称为简单回路或简单环
  • 连通图:任意两个顶点都存在路径的图;如果该图是有向图则称强连通图
  • 弱连通图:将有向图的所有有向边替换为无向边,得到的图称为原图的基图,基图为连通图的有向图是弱连通图
  • 权:与边相关的数值;如果一个图的边有权则是有权图,否则就是无权图,有权图简称网

基本操作:

  • 按照顶点集和边集构造图
  • 销毁已存在的图
  • 获取顶点在图中的位置
  • 返回图中指定顶点的值
  • 在图中插入新的顶点
  • 删除图中的顶点及其相关的边
  • 在图中添加边
  • 在图中删除边
  • 深度优先遍历并执行调用
  • 广度优先遍历并执行调用

二、图的遍历

从图中某一顶点出发访问图中其余顶点,且每一个顶点仅被访问一次,这个过程称为图的遍历。根据搜索方法的不同,又可以划分为两种搜索策略:

  • 深度优先搜索(DFS):类似于树的先序遍历。从图中某个顶点V出发,访问该顶点,然后依次从V的未被访问的邻接点出发继续深度优先遍历图中的其余顶点,直至图中所有和V有路径相通的顶点都被访问完为止。
  • 广度优先搜索(BFS):是一个分层遍历的过程,和树的层序遍历算法类同。从图的某一顶点V出发,访问此顶点后,依次访问V的邻接点;然后分别从这些邻接点出发,直至图中所有已被访问的顶点的邻接点都被访问到。

三、存储结构

1、邻接矩阵

存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边的信息,若图有N个顶点,则邻接矩阵就是一个N×N的方阵。 对于有向图和无向图,矩阵第[i][j]个元素存储记录图的第i个顶点是否能到达第j个顶点,若能记为1,不能记为0,i和j相等也记为0,而无向图的边视为双向边。特别的,无向图的邻接矩阵是一个对称矩阵。 无向图.png 有向图.png 对于有权的图,第[i][j]个元素存储记录图的第i个顶点到达第j个顶点的权,不能到达的记为∞,i和j相等记为0。 有权图.png

2、邻接表

对于边数相对顶点较少的图,邻接矩阵存在对存储空间的极大浪费的。因此我们考虑另外一种存储结构方式:邻接表,即数组与链表相结合的存储方法。用一个一维数组存储图中顶点信息,用单链表存储所有顶点的邻接点,无向图称为顶点的边表,有向图称为顶点的出边表,如果存储的是入边表,则称为有向图的逆邻接表,如果是有权图,可以在边表结点定义中添加一个数据项来存储权值

3、十字链表

对于有向图来说,邻接表是有缺陷的,关心了出度问题,想了解入度就必须要遍历整个图才能知道,反之,逆邻接表也是类似的情况。可以把邻接表与逆邻接表结合起来,即有向图的一种存储方法十字链表。即在有向图的邻接表的边表结点定义中再增加一个入度指针。 十字链表.png

4、邻接多重表

虽然邻接表是无向图的一种很有效的存储结构,在邻接表中容易求得顶点和边的各种信息. 但是,在邻接表中每一条边(vi,vj)有两个结点,分别在第i个和第j个链表中,这给某些图的操作带来不便。如对已被搜索过的边作记号或删除一条边等,此时需要找到表示同一条边的两个结点。可采用邻接多重表。 邻接多重表.png

5、边集数组

由两个数组一维数组组成。一个一维数组存储图中顶点信息,另一个一个存储边信息,边数组的每个数据元素由一条边的起点下标、终点下标组成,如果是有权图,可以增加一个数据项存储权。 边集数组.png

6、存储结构比较

存储方法实现方法优点缺点
邻接矩阵二维数组顶点间关系和度易得占用空间大
邻接表链表数组顶点的出度易得顶点间关系和入度不易得
十字链表链表数组易得出度和入度结构复杂
邻接多重表链表数组易得顶点间的关系结构复杂
边集数组一维数组空间要求小顶点间关系和度不易得

© 2026 我的博客

🌱 Powered by Hugo with theme Dream.

关于这个博客

关于博客

记录软件开发过程的一些知识和技巧,提升自我

关于博主

除了才华一无所有~~ 薪尽自然凉~~ 强迫症患者~~ 热爱古风~~