chap2-课件-3.ppt

* 上一张 下一张 结 束 数据结构与算法 图型结构 图的遍历 图的存储结构 图的概念 （1）图的定义 图是由顶点集V和顶点间的关系集合E（边的集合）组成的一种数据结构，可以用二元组定义为：G=（V，E）。 例如，对于图2-14所示的无向图G1和有向图G2，它们的数据结构可以描述为：G1=(V1,E1), 其中 V1={a,b,c,d},E1={(a,b),(a,c),(a,d),(b,d),(c,d)}，而G2=(V2,E2)， 其中V2={1,2,3}，E2={1,2,1,3,2,3,3,1}。 1．图的概念 （2）图的基本术语 有向图和无向图 在图中，若用箭头标明了边是有方向性的，则称这样的图为有向图，否则称为无向图。如图2-14中，G1为无向图，G2为有向图。 在无向图中，一条边（x，y）与（y，x）表示的结果相同，用圆括号表示，在有向图中，一条边x,y与y,x表示的结果不相同，故用尖括号表示。〈x，y〉表示从顶点x发向顶点y的边，x为始点，y为终点。有向边也称为弧，x为弧尾，y为弧头,则〈x，y〉表示为一条弧,而〈y，x〉表示y为弧尾，x为弧头的另一条弧 。 完全图、稠密图、稀疏图 具有n个顶点，n(n-1)/2条边的图，称为完全无向图，具有n个顶点，n(n-1) 条弧的有向图,称为完全有向图。完全无向图和完全有向图都称为完全图。 对于一般无向图，顶点数为n，边数为e，则 0≤e ≤n(n-1)/2。 对于一般有向图，顶点数为n，弧数为e， 则 0≤e≤n(n-1) 。 当一个图接近完全图时，则称它为稠密图，相反地，当一个图中含有较少的边或弧时，则称它为稀疏图。 度、入度、出度 在图中，一个顶点依附的边或弧的数目，称为该顶点的度。在有向图中，一个顶点依附的弧头数目，称为该顶点的入度。一个顶点依附的弧尾数目，称为该顶点的出度，某个顶点的入度和出度之和称为该顶点的度。 另外，若图中有n个顶点，e条边或弧，第i个顶点的度为di，则有e= 子图 若有两个图G1和G2， G1=(V1,E1)， G2=(V2,E2)， 满足如下条件： V2?V1 ，E2? E1，即V2为V1的子集，E2为E1的子集，称图G2为图G1的子图。 图和子图的示例。 权 在图的边或弧中给出相关的数，称为权。 权可以代表一个顶点到另一个顶点的距离，耗费等，带权图一般称为网。 带权图的示例。 连通图和非连通图 在无向图中，若从顶点i到顶点j有路径，则称顶点i和顶点j是连通的。若任意两个顶点都是连通的，则称此无向图为连通图，否则称为非连通图。 连通图和非连通图示例。 在有向图中，若从顶点i到顶点j有路径，则称从顶点i和顶点j是连通的，若图中任意两个顶点都是连通的，则称此有向图为强连通图，否则称为非强连通图。 强连通图和非强连通图示例。 强连通图和非强连通图 连通分量和强连通分量 无向图中，极大的连通子图称为该图的连通分量。显然，任何连通图的连通分量只有一个，即它本身，而非连通图有多个连通分量。 对于图2-17(b)非连通图，它的连通分量见图。 图2－17(b) 有向图中，极大的强连通子图为该图的强连通分量。显然，任何强连通图的强连通分量只有一个，即它本身，而非强连通图有多个强连通分量。 对于图2-18(b)非强连通图，它的强连通分量见图。 图2－18(b) 2． 图的存贮结构 （1） 图的邻接矩阵表示 在邻接矩阵表示中，除了存放顶点本身信息外，还用一个矩阵表示各个顶点之间的关系。若（i，j）∈E(G)或〈i，j〉∈E(G), 则矩阵中第i行 第j列元素值为1，否则为0 。 图的邻接矩阵定义为： 1 若（i,j）∈E(G)或〈i,j〉∈E(G) A[i][j]= 0 其它情形 例如，对图2-21所示的无向图和有向图，它们的邻接矩阵见图2-22。 从无向图的邻接矩阵可以得出如下结论 （1）矩阵是对称的； （2）第i行或第i 列1的个数为顶点i 的度； （3）矩阵中1的个数的一半为图中边的数目； （4）很容易判断顶点i 和顶点j之间是否有边相连（看矩阵中i行j列值是否为1）。 从有向图的邻接矩阵可以得出如下结论 （1） 矩阵不一定是对称的； （2） 第i 行中1的个数为顶点i 的出度； （3） 第i 列中1的个数为顶点 i的入度； （4） 矩阵中1的个数为图中弧的数目； （5） 很容易判断顶点i 和顶点j 是否有弧相连。 建立无向图的邻接矩阵 void creatadj(graph g) { int i, j,k ; for (k=1; k=n; k