图及其存储结构.ppt

1.图的有关概念 1.图的有关概念 1.图的有关概念 1.图的有关概念 1.图的有关概念 1.图的有关概念 2.图的遍历 1.图的数组表示法 1.图的数组表示法 1.图的数组表示法 1.图的数组表示法 2.数组表示法前提下图的输入 2.数组表示法前提下图的输入 3.图的邻接表表示法 3.图的邻接表表示法 3.图的邻接表表示法 4.邻接表表示法前提下图的输入 4.邻接表表示法前提下图的输入 4.邻接表表示法前提下图的输入 * * 图及其存储结构 ①图(Graph)的ADT定义：图是n( n≥0 )个结点的有限集合。在任意一个图中任意两个结点之间都可能相关。图的ADT定义如下： 一、基本概念 数据对象V： V是具有相同特性的数据元素的集合，并称为顶点集合。 数据关系R： R={E} E={v,w|v,w∈V ,且有谓词P(v,w),v,w表示从v到w的弧，谓词P(v,w)定义了弧v,w上的信息或权值} 基本操作P： 详见P.156 。 图的二元组表示：G=(V，E) E即为图中边或弧的集合。 ②图的有关术语： 一、基本概念 图中的数据元素称为顶点； 有向图； 弧； 弧头； 弧尾； 无向图； 边； *定理：若用e表示有向图或无向图中弧或边的条数，即e=|E|,则有： 在有向图中： 0≤e≤n(n-1) 在无向图中： 0≤e≤n(n-1)/2 具有n(n-1)/2条边的无向图称为完全图： 具有n(n-1)条边的有向图称为有向完全图： a b c d 0 1 2 3 ②图的有关术语： 一、基本概念 顶点的度； 有向图中顶点的度是该顶点的入度与出度之和。 无向图中顶点的度是与该顶点相关联的边的条数。 子图：对于G1=(V1,E1),G2=(V2,E2),若V2 V1，E2 E1，则称G2是G1的子图。 回路（环）：若一条路径上的顶点均不相同则该路径称为简单路径；除了顶点和终点相同外，路径上的其他顶点均不相同的路径称为回路或环。 a b c d 0 1 2 3 ②图的有关术语： 一、基本概念 无向图中任意两个顶点都是连通的，则该图为连通图。有向图中任何有序顶点对之间都有有向路径，则称该图是强连通的。无向图中最大的连通子图称为该图的连通分量；有向图中相应地称为强连通分量。 a b c d 0 1 2 3 ②图的有关术语： 一、基本概念 一个连通无向图的生成树是该图的一个连通分量，它包含有该图的所有n个顶点以及连接这n个顶点的（n-1）条边。 边或弧上带权值的图称为带权图或网（分为无向网和有向网）。 一个无向图的所有生成树中，边上的权值之和最小的生成树称为该图的最小生成树或最小代价生成树。 a b c d e f 6 5 5 1 2 5 6 4 6 3 ②图的有关术语： 一、基本概念 图中顶点的“序号”及其邻接点的“序号”： 由于图中顶点之间不存在全序关系，所以无法将图中顶点进行线性排序。但为了实现图的存储结构，我们必须给每个顶点附加一个人为规定的“序号”。这个序号即称为该顶点在图中的位置。 对于任意一个顶点而言，若它有两个以上的邻接点，则它的邻接点也有所谓“第一个邻接点”， “第二个邻接点”，......，这个顺序也称为邻接顺序。 一、基本概念 图的遍历：从图中某一顶点出发按一定规律沿着图中的边或弧访问每一顶点一次且仅一次的操作称为对图的遍历。 *图的遍历有两种方法：深度优先遍历和广度优先遍历 *若图是连通的或是强连通的，则遍历过程所经过的边（或弧）加上图中所有顶点就是图的一棵生成树。 *对于不连通图而言，从某一连通分量中的某一顶点出发执行一次“遍历”算法可得该连通分量的生成子树。若干次使用上述方法可得到图的生成森林。 二、存储结构 *思想：用两个数组分别存储数据元素(顶点)的信息和数据元素之间的关系：即用一个一维数组vexs存放各顶点的有关信息；用一个二维数组arcs存放各条边或弧的有关信息(一般情况下也即存放边或弧上的权值；对于边或弧上无权值的图而言，边或弧上的权值为1时表示该条弧或边的存在，若两顶点之间没有边或弧，则设置该条边或弧上的权值为0)。 二、存储结构 #define INF