数据结构（第八章图）DataStructures胡学钢张晶计算机与.ppt

第八章 图 (Graph) 第八章 图（Graph) 8.1 基本概念和运算 8.2 图的存储 8.3 图的遍历 8.4 最小生成树 8.5 有向无环图的应用 8.6 最短路径 8.1 基本概念和运算 图 —— 由顶点集V和连接顶点的弧集E所组成的结构， 记作 G = ( V, E )。 其中弧的形式为Vi,Vj， 表示从顶点Vi到Vj之间有一条弧，图形表示为： Vi — Vj ----有向图 例：如右图中的G1就是一个有向图： 其中： 顶点集合 V={1，2，3，4} 弧集 E={ 1,2, 1,3, 2,4, 3,4, 4,1 } 8.1 基本概念和运算 如果顶点间的关系是相互的， 即弧的两端没有方向，则图为无向图。 其中的弧称为边。 边的形式为(Vi,Vj)， 图形表示为： Vi —— Vj 例：如右图中的G2就是一个无向图： 其中： 顶点集合 V={1，2，3，4} 边集 E={ （1,2）,（1,3）,（1,4） （2,4）,（3,4） } 8.1 基本概念和运算 若G中每条边（弧）对应一个数值 ——表示关系的程度，则称图G为网络。 例： 图G3 就是一个网络 对图G = ( V, E )，若存在G1=(V1，E1)， 满足V1≤V，E1≤E。则G1是G的子图。 例如：右图G4 就是G2 的子图。 8.1 基本概念和运算 顶点间关系： 如果 Vi,Vj∈E 则称—— Vi，Vj相邻接， Vi邻接到Vj，Vj邻接自Vi。 例如，右 图中， V1邻接到V2，V4邻接自V3 若( Vi,Vj )∈E——则称Vi，Vj相邻接 顶点的度 —— 顶点的邻接点的数目。 有向图中：入度，出度。 度＝入度＋出度。 8.1 基本概念和运算 路径 ——若 顶点序列Vi1，Vi2，…，Vik， 满足 Vil，Vi(l+1)∈E或 者(Vil，Vi(l+1))∈E）（l=1,2,…,k-1）， 则该顶点序列Vi1，Vi2，…，Vik 构成一条路径。 例: 图G1中，1,2,4,1,3,4是一条路径 简单路径 —— 中间经过的顶点不重复的路径。 例:图G1中，( 1,2,4 ) ( 1,3,4 ) ( 1,3,4,1 ) 都是简单路径。 回路 —— 首尾相同的路径。 例如， ( 1,3,4,1 ) 简单回路 —— 简单路径 + 回路 8.1 基本概念和运算 若无向图中任意两点间都存在路径 —— 则称为连通图。 否则，称为不连通图（非连通图）。 非连通图包含若干连通分量----极大连通子图。 若有向图中的任意两点间可以互相到达 ——则称为强连通图。 8.1 基本概念和运算 若无向图中任意两点间都有一条边 ——则称为无向完全图。 （共有n (n-1) / 2条边） 若有向图中每个顶点到其余各点均有一条弧 ——则称为有向完全图。 （共有n (n-1) 条边） 8.1 基本概念和运算 若无向图满足：连通并且无回路 ——则称为树。 树的定义有如下几个等价的描述： 有最少边数的连通图。 有n-1条边的连通图。 连通的无环图。 有向树 —— 如果在有向图中， 有一个顶点的入度为0，其余顶点的入度为1， 则称此图为有向树。