ch7图new.ppt

第7章 图 例 1.3 铺设煤气管道问题 怎样铺设管道最省钱（图） 7.1 图的定义和基本术语 图(Graph)G是由两个集合V和E组成的,表示为 G=（V，E） V：有限非空的顶点集合(顶点 vertex)— 数据元素 E：由所有两个顶点对之间的弧（边）组成的集合 （边Edge） — 数据关系 弧和有向图 如下图(a)是一个有向图G，可形式地表示为： G=(V,E) V={a，b，c，d，e} E={a,b，a,c，a,e，c,d，c,e，d,a，d,b，e,d} E是有向边（也称弧）的有限集合，弧是顶点的有序对，记为v,w，v,w是顶点，v为弧尾，w为弧头 边和无向图 如图(b)所示的是一个无向图G，可形式地表示为： G=(V,E) V={a，b，c，d} E = {(a,b),(a,c),(a,d),(b,d),(c,d)} E(G)是边的有限集合，边是顶点的无序对，记为（v,w）或（w,v)，并且（v,w)=(w,v) 权与网 权——与图的边或弧相关的数叫权 网——带权的图叫网 子图 子图——如果图G(V,E)和图G‘(V’,E‘),满足： V’?V E’?E 则称G‘为G的子图，即取图的一部分或全部的顶点和边（弧）构成的图称为子图。 有向完全图——n个顶点的有向图最大弧数是n(n-1) 无向完全图——n个顶点的无向图最大边数是n(n-1)/2 邻接点、度 若顶点v、w之间存在一条边（弧），则称v和w互为邻接点，边(v、w)与顶点v、w相关联。 顶点的度 无向图中，顶点的度TD为与每个顶点相连的边数 有向图中，顶点的度分成入度与出度 入度ID：以该顶点为头的弧的数目 出度OD：以该顶点为尾的弧的数目 路径、路径长度、回路、简单回路 路径——路径是顶点的序列V={Vi0,Vi1,……Vin}，满足(Vij-1,Vij)?E 或 Vij-1,Vij?E,(1j?n) 路径长度——沿路径边的数目或沿路径各边权值之和 回路——第一个顶点和最后一个顶点相同的路径叫回路 简单路径——序列中顶点不重复出现的路径叫~ 简单回路——除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫~ 连通图 连通——从顶点V到顶点W有一条路径，则说V和W是连通的 连通图——图中任意两个顶点都是连通的叫~ 强连通图——有向图中，如果对每一对Vi,Vj?V, Vi?Vj,从Vi到Vj 和从Vj到 Vi都存在路径，则称G是~ 非连通图和（强）连通分量 非连通图——图中只要有两个顶点不是连通的叫~ （强）连通分量——非连通图的每一个极大连通子图叫~ 生成树和生成森林 假设一个连通图有n个顶点和e条边，若其中某n-1条边和n个顶点构成一个极小连通子图，则称该极小连通子图为此连通图的生成树。一个连通图可以找到若干个生成树。 对于非连通图，各个连通分量的生成树便构成了该非连通图的生成森林。 图的基本操作 (1) CreateGraph(G,V,VR)：图的创建操作。 初始条件：V是图的顶点集，VR是图中弧的集合。 操作结果：按V和VR的定义构造图G。 (2) LocateVex(G,v)：顶点定位函数。 初始条件：G已经存在，v是一个顶点。 操作结果：返回v在G中的位置，若G中无此顶点，则返回“空”。 (3) FirstAdj(G,v)：求第一个邻接点函数。 初始条件：G已经存在，v是G中某个顶点。 操作结果：返回v的第一个邻接点，若v在G中无邻接点，则返回“空”。 (4) NextAdj(G,v,w)：求下一个邻接点函数。 初始条件：G已经存在，v是G中某个顶点，w是v的一个邻接点。 操作结果：返回v的邻接点中w之后的下一个邻接点，若无下一邻接点，则返回“空”。 (5) getVexVal(G,v)：取顶点元素值函数。 初始条件：G已经存在，v是G中某个顶点。 操作结果：返回v的值。 (6) PutVex(G,v,e)：修改顶点元素操作。 初始条件：G已经存在，v是G中某个顶点。 操作结果：将v的元素值改为e。 (7) InsertVex(G,v)：增加顶点操作。 初始条件：G已经存在，且G中不存在顶点v。 操作结果：在G中增加一个新顶点v。 (8) deletevex(G,v)：删除顶点操作。 初始条件：G已经存在，v是G中某个顶点。 操作结果：从G中删除顶点v以及与v相关的弧或边。 (9) InsertArc(G,v,w)：增加弧（或边）操作。 初始条件：G已经存在，v和w是G中的两个顶点。 操