数据结构与算法|学习笔记--数据结构与算法基础（青岛大学-王卓）--第六章图算法|图|数据结构图|数据结构

视频链接:

文章图片

数据结构与算法基础（青岛大学-王卓）–第六章图
本章知识框架:

文章图片

目录:

- - 1.图的定义和基本术语
  - 2.案例引入
  - 3.图的类型定义(抽象数据类型)
  - 4.图的存储结构
  - 5.图的遍历
  - 6.图的应用

1.图的定义和基本术语

图表示多对多关系
图是由顶点(V集合)和边(E集合)构成,G=(V,E)
无向图:每条边都是无方向的
有向图:每条边都是有方向的

文章图片

上图G1的顶点V集合={V1,V2,V3,V4}; E集合={V1->V3,V1->V2,V3->V4,V4->V5}
上图G2的顶点V集合={V1,V2,V3,V4}; E集合={E1,E2,E3,E4,E5,E6,E7}

文章图片

完全图:任意二个点都有一条边相连

文章图片

稀疏图,稠密图,网,邻接,关联(依附)

文章图片

弧:有向图中的边(为了区分有向图和无向图的边)

文章图片

稀疏图(e表示边,n表示顶点的数目):

文章图片

稠密图:
(e>=nlogn)
网:边/弧带权值

文章图片

邻接：
(V1,V2)表示V1,V2互为邻接点

文章图片

V1邻接到V2或V2邻接于V1

文章图片

有向图和无向图的度

文章图片

无向图V0的度为2(红色边的数量):

文章图片

有向图V0的入度为1:

文章图片

有向图V0的出度为2:

文章图片

有向树:在有向图中仅有一个顶点的入度为0其余顶点的入度为1的图

文章图片

路径,路径长度,回路(环),简单路径,简单回路(简单环)

文章图片

连通图

文章图片

无向图的连通图:
下图连通图:V0可以去到任意顶点V1,V2,V3,V4,同理V1,V2,V3,V4也可以

文章图片

下图非连通图:V0,V1,V2,V3无法去到V4,V5同理V4,V5无法去到V0~V3

文章图片

有向图的连通图:
下图强连通图:V0可以去到任意顶点V1,V2,V3,同理V1,V2,V3也可以

文章图片

下图非强连通图:V1无法去到V0,V2,V3

文章图片

权与网

文章图片

子图

文章图片

无向图连通分量

G1,G2为G的连通子图并且都为极大连通子图(不管是G2或G1的顶点只要加入另外一个子图就会不在连通),G1,G2也称为G的连通分量

文章图片

有向图强连通分量

文章图片

下图是一个非强连通图(V1无法到达V0,V2,V3),将V1去掉看成一个子图,这时候V1和(V0,V2,V3)分别为G的强连通分量

文章图片

极小连通子图,生成树,生成森林

极小连通子图:该子图是G的连通子图，在该子图中删除任何一条边子图不再连通

文章图片

下图就是一个极小连通子图,删除任意一条边就不再连通

文章图片

连通图G1的生成树:包含G1中所有顶点的极小连通子图

文章图片

2.案例引入

六度空间理论

文章图片
六度空间理论的验证

文章图片

3.图的类型定义(抽象数据类型)

属性

文章图片

操作

文章图片

文章图片

4.图的存储结构

顺序存储结构,图是没有顺序存储结构的,但是可以通过二维数组来表示元素之间的关系,这种方式称为数组表示法(邻接矩阵)
链式存储结构,链式存储结构的前驱和后驱不知道要定义多少(图是多对多关系)所以无法使用多重链表,但是可以通过邻接表,邻接多重表，十字链表来表示

数组表示法(邻接矩阵)

文章图片

无向图的邻接矩阵表示法

文章图片

有向图的邻接矩阵表示法

文章图片

文章图片
网(即有全图)的邻接矩阵表示法

文章图片
【数据结构与算法|学习笔记--数据结构与算法基础（青岛大学-王卓）--第六章图】邻接矩阵利与弊
利:
文章图片

弊:

文章图片

邻接表表示法(链式)

文章图片

文章图片
无向图

文章图片
有向图

文章图片