计算机专业 80。 网上教学改革 ● 数据结构（本） 授课教师：范颖
计算机专业 网上教学改革 数 据 结 构（本） 授课教师：范颖
二、第七章图解析 本章课程主要介绍图的定义，图的三种存储结构 即邻接矩阵。邻接表和边集数组的表示方法和生 成算法，图的深度优先搜索和广度优先搜索遍历 的方法和算法，理解图的最小生成树、图的最短 路径和图的拓扑排序。 www.open.ha.cn 6
www.open.ha.cn 二、第七章图解析 ▪ 本章课程主要介绍图的定义，图的三种存储结构， 即邻接矩阵。邻接表和边集数组的表示方法和生 成算法，图的深度优先搜索和广度优先搜索遍历 的方法和算法，理解图的最小生成树、图的最短 路径和图的拓扑排序
二、第七章图解析 ■1、学习图需要知道的一些基本概念。 (1)端点和邻接点 例： B A D E 无向图 有向图 ·A、B为边（A,B)的两个端点。 ■A、 B两点互为邻接点。 www.open.ha.cn
www.open.ha.cn 二、第七章图解析 ▪ 1、学习图需要知道的一些基本概念。 （1）端点和邻接点 例： ▪ A、B为边（A，B）的两个端点。 ▪ A、B两点互为邻接点。 A C D E B 无向图 A C D E B 有向图
二、第七章图解析 ·1、学习图需要知道的一些基本概念。 (2)顶点的度、入度和出度 例： B ⊙ E (D 无向图 有向图 ·无向图中顶点的度等于以顶点为端点的边的数目。 ·有向图中顶点的度等于入度和出度之和。 ■ 图中n个顶点度数之和是所有边数e的2倍。 www.open.ha.cn
www.open.ha.cn 二、第七章图解析 ▪ 1、学习图需要知道的一些基本概念。 （2）顶点的度、入度和出度 例： ▪ 无向图中顶点的度等于以顶点为端点的边的数目。 ▪ 有向图中顶点的度等于入度和出度之和。 ▪ 图中n个顶点度数之和是所有边数e的2倍。 A C D E B 无向图 A C D E B 有向图
二、第七章图解析 ·1、学习图需要知道的一些基本概念。 (2)顶点的度、入度和出度 例： (A B A c D E D E 无向图 有向图 ■无向图中C顶点的度为4。 ·有向图中C顶点的入度为1，出度为3，C顶点的度 数为4。 ■图中五个顶点的度数之和为边数的2倍，即16。 www.open.ha.cn
www.open.ha.cn 二、第七章图解析 ▪ 1、学习图需要知道的一些基本概念。 （2）顶点的度、入度和出度 例： ▪ 无向图中C顶点的度为4。 ▪ 有向图中C顶点的入度为1，出度为3，C顶点的度 数为4。 ▪ 图中五个顶点的度数之和为边数的2倍，即16。 A C D E B 无向图 A C D E B 有向图
二、第七章图解析 ■1、学习图需要知道的一些基本概念。 (3)完全图、稠密图、稀疏图 ·完全图：若无向图中的每两个顶点之间都存在着 一条边，有向图中都存在着方向相反的两条边。 无向完全图中存在n(n-1)/2条边，有向图中存在 n(n-1)条边。 ◆ 稠密图：图中的边数接近完全图。 ■稀疏图：图中的边数远小于完全图。 B B A B 完 A 图 www.open.ha.cn D D E
www.open.ha.cn 二、第七章图解析 ▪ 1、学习图需要知道的一些基本概念。 （3）完全图、稠密图、稀疏图 ▪ 完全图：若无向图中的每两个顶点之间都存在着 一条边，有向图中都存在着方向相反的两条边。 无向完全图中存在n(n-1)/2条边，有向图中存在 n(n-1)条边。 ▪ 稠密图：图中的边数接近完全图。 ▪ 稀疏图：图中的边数远小于完全图。 A D E A B C D B 完 全 图 A C D B
二、第七章图解析 ■1、学习图需要知道的一些基本概念。 (4)路径和回路 ·路径：一个从V到V的顶点序列。 ·路径长度：路径上经过的边的数目。 ·简单路径：路径上的顶点都不相同。 ·回路（环）：起点与终点相同的路径。 ▣例： 路径：1,2,3,5,6,3 路径长度：5 简单路径：1,2,3,5 回路：1,2,3,5,6,3,1 1 5 6 简单回路：3,5,6,3 www.open.ha.cn
www.open.ha.cn 二、第七章图解析 ▪ 1、学习图需要知道的一些基本概念。 （4）路径和回路 ▪ 路径：一个从Vi到Vj的顶点序列。 ▪ 路径长度：路径上经过的边的数目。 ▪ 简单路径：路径上的顶点都不相同。 ▪ 回路（环）：起点与终点相同的路径。 ▪ 例： 2 4 5 1 3 6 路径：1，2，3，5，6，3 路径长度：5 简单路径：1，2，3，5 回路：1，2，3，5，6，3，1 简单回路：3，5，6，3
二、第七章图解析 1、学习图需要知道的一些基本概念。 (5)连通和连通分量 ·连通：无向图中两个顶点有路径。 连通图：任意两个顶点都连通。 ■} 连通分量：非连通图中几个单独的连通子图。 例： 连通图的连通分量只有一个。 2 5 非连通图有多个连通分量。 1 6 www.open.ha.cn
www.open.ha.cn 二、第七章图解析 ▪ 1、学习图需要知道的一些基本概念。 （5）连通和连通分量 ▪ 连通：无向图中两个顶点有路径。 ▪ 连通图：任意两个顶点都连通。 ▪ 连通分量：非连通图中几个单独的连通子图。 ▪ 例： 连通图的连通分量只有一个。 非连通图有多个连通分量。 2 4 5 1 3 6
二、第七章图解析 ■1、学习图需要知道的一些基本概念。 (6)强连通图和强连通分量 ■子 连通：有向图中顶点V到V有路径，则称V到Vj 是连通的。 强连通图：图中任意两个顶点互相都连通。 强连通分量：有向图中极大连通子图。 ·下面是一个非连通图，包涵三个强连通分量： B B G (D www.open.ha.cn
www.open.ha.cn 二、第七章图解析 ▪ 1、学习图需要知道的一些基本概念。 （6）强连通图和强连通分量 ▪ 连通：有向图中顶点Vi到Vj有路径，则称Vi到Vj 是连通的。 ▪ 强连通图：图中任意两个顶点互相都连通。 ▪ 强连通分量：有向图中极大连通子图。 ▪ 下面是一个非连通图，包涵三个强连通分量： A C D E B F G A C D B E F G
二、第七章图解析 ·1、学习图需要知道的一些基本概念。 (6)强连通图和强连通分量 ■ 强连通图的强连通分量只有一个。 非强连通图有多个强连通分量。 www.open.ha.cn 可
www.open.ha.cn 二、第七章图解析 ▪ 1、学习图需要知道的一些基本概念。 （6）强连通图和强连通分量 ▪ 强连通图的强连通分量只有一个。 ▪ 非强连通图有多个强连通分量