#笨鸟先飞# 数据结构与算法基础 课程笔记 第六章 图

图的定义和基本术语

• 图：G=( V , E ) Graph=（Vertex，Edge）

1. V：顶点（数据元素）的有穷非空集合；

2. E：边的有穷集合。

• 无向图：每条边都是无方向的

• 有向图：每条边都是有方向的

• 完全图：任意两个顶点都有一条边相连

• 稀疏图：有很少边或弧的图（e<n logn）

• 稠密图：有较多边或弧的图

• 网：边或弧带权的图

• 邻接：有边或弧相连的两个顶点之间的关系

1. 存在（v1，v2），则称v1和v2互为邻接点；

2. 存在<v1，v2>，则称v1邻接到v2，v2邻接于v1。

• 关联（依附）：边或弧与顶点之间的关系；存在（v1，v2）或<v1，v2>，则称该边或弧关联于v1和v2

• 顶点的度：与该顶点相关联的边的数目，记为TD(v)

1. 在有向图中，顶点的度等于该顶点的入度与出度之和；

2. 顶点v的入度是以v为终点的有向边的条数，记作ID(v)；

3. 顶点v的出度是以v为始点的有向边的条数，记作OD(v)。

• 路径：接续的边构成的顶点序列

• 路径长度：路径上的边或弧的数目或权值之和

• 回路（环）：第一个顶点和最后一个顶点相同的路径

• 简单路径：除路径起点和终点可以相同外，其余顶点均不相同的路径

• 简单回路（简单环）：除路径起点和终点相同外，其余顶点均不相同的回路

• 连通图（强连通图）：在无（有）向图G=（V，E）中，若对任何两个顶点v、u都存在从v到u的路径，则称G是连通图（强连通图）。

• 子图：

• 连通分量：无向图G的极大连通子图·称为G的连通分量。

极大连通子图的意思是：该子图是G的连通子图，将G的任何不在该子图中的顶点加入，子图不再连通。

• 强连通分量：有向图G的极大强连通子图称为G的强连通分量。

极大强连通子图的意思是：该子图是G的强连通子图，将G的任何不在该子图中的顶点加入，子图就不再是强连通的。

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

• 生成树：包含无向图G所有顶点的极小连通子图

• 生成树林：对非连通图，由各个连通分量的生成树组成的集合

图的类型定义

图的抽象数据类型定义

图的基本操作

图的存储结构