数据结构 第6章 图【PPT课件】

1 2 的基本概念 的存储结构 接矩阵表示法 接表 的遍历化 度优先搜索 度优先搜索 的连通分量计算 3 一、图的定义 图 G 是由集合 组成，记成 G=（ V， E） 其中： V 顶点集 （非空）； E 边集 （可空）。 边是顶点的有序对或无序对。 （边反映了两顶点之间的关系） 有向图 ：边是顶点的有序对的图。 （图中每条边都用箭头指明了方向） 无向图 ：边是顶点的无序对的图。 的基本概念 4 例： V( 1， 2， 3， 4 E( (1,2)， (1,3)， (1,4)， (2,3)， (2,4)， (3,4) （图 （无向图） V( 1， 2， 3， 4 ， 5， 6， 7 E( (1,2)， (1,3)， (2,4)， (2,5)， (3,6)， (3,7) （图 V( 1， 2， 3 E( ， ， （图 （有向图） 注： 1）边集可空； 2）边集中不允许出现相同的边。 5 二、图的基本术语 顶点 (图中的数据元素； 有向图中 ,顶点 顶点 也称 弧 ； 弧 头 （终端点）：箭头端； 弧 尾 （初始点）：无箭头端； 完全图 无向完全图： 边数 =n*(2的无向图； 有向完全图： 边数 =n*(有向图； (顶点数 n) 权 与图中的边相关的数； 子图 图 , 若有 V(G) V(G)和 E(G) E(G),则称 G 为图 （图 （图 （图 6 邻接 若 (j)E(G) ，则称 关联 若 (j)E(G) ，则称边 (j)关联于顶 点 j; 注： 1）邻接是指顶点之间的关系，而关联是指边与 顶点间的关系。 2） 若弧 E(G) ， 则称 度 无向图：顶点 D(有向图 出度 :顶点 i) 入度 :顶点 i) 度 :有向图的度 =入度 +出度； D( D( i)+i) 7 注： 图中边数 e= 2 1 n i=1 D（ （一边带二度，两度组成一边） 路径 图中，顶点 ,q 且 对无向图，边 ( ,(q); 对有向图，弧 , ,); 路径长度 路径上边或弧的数目； 简单路径 除第一个和最后一个外，其余各顶 点均不相同的路径； 8 回路 第一个和最后一个顶点相同的路径，也称环； 简单回路 第一个和最后一个顶点相同的简单路径； 注：回路中可以有多个圈，而简单回路只能有一个圈。 连通 无向图中，若从顶点 称 连通图 和 连通分量 针对无向图而言 9 定 义 例 无 向 图 连通图 连通 分量 图中 每对 顶点 间都连通 ; 中 极大 的连通子图（再扩大一点就不连通） ( ( （ 图，但它有 两个连通分 ( 量） 有向图 强连通图 强连通分量 图中任意一对顶点 有从个顶点间双向连通。 有向图的 极大强连通子图。 ( 图 生成树 含有该连通图的全部顶点的一个极 小连通子图 若连通图 n，则 边数大于 G中一定 有环 。 边数小于 G中一定 不连通。 生成森林 在非连通图中，每个连通分量都可得到一个极小连通子图，也就是生成树。这些生成树就组成了一个非连通图的生成森林。 10 图的基本运算 建立图 ,V,E) 取顶点信息 ,u) 取边信息 ,u,v) 查询第一个邻接点 ,u) 查询下一个邻接点 ,u,v) 插入顶点 ,v) 删除顶点 ,v) 插入边 ,v,w) 删除边 ,v,w) 遍历图 ,11 12 接矩阵表示法 的存储结构 1、图的邻接矩阵 表示图的各顶点之间关系的矩阵。 定义 设 G=(V,E)是 邻接矩阵为下列 Aij= 1 若 (j)或 E(G) 0 否则 13 0 1 1 1 1 0 1 0 1 1 0 1 1 0 1 0 （图 （图 0 1 0 1 0 1 0 0 0 1 2 3 123 例： 结论： （ 1）无向图的邻接矩阵是对称的； （ (j) E(G)，则 (i) E(G) ） （ 2）从邻接矩阵容易判断任意两顶点间是否有边相联； 容易求出各顶点的度； 无向图： 顶点 (矩阵中第 总和 有向图： i)=矩阵中第 总和 I D(矩阵中第 总和 14 2、 带权图 (网 )的邻接矩阵 Aij= 若 (j)或 E(G) （ 3、邻接矩阵的类型定义 0; /顶点信息 /邻接矩阵 /顶点数，边数 4、建立无向带权邻接矩阵： 将矩阵 然后读入边和权值（ i， j， 将 法如下： 15 g) i,j,n,e,w; %d %d”,&n,&e); g-n; g-e; i=0;i+) %c”,& g-i= i=0;i+) j=0;j+) g-ij=k=0;k+) %d %d %d”,&i, &j,&w); g-ij=w; g-ji=w; 16 1. 定义： 对图 单链表（称 边表 ） 链接图中与顶点 结点形式： 邻接点域 （顶点域）： 存放与顶点 j； 链域 ：指向 每个链表均设一表头结点（以向量存储，称 顶点表 ） 表头结点： i第 Vi 存放顶点 Vi 指向 接表表示法 7 3. 结论： 1） 无向图，则其邻接表的表头结点数为 n， 链表结点总数为 2e； 2）对于 无向图，第 对于 有向图，第 3）在边稀疏时，邻接表比邻接矩阵省单元； 4）邻接表表示在检测边数方面比邻接矩阵表示效率 要高。 2. 例： 见黑板（ 1、 18 2 4 2 3 4 5 2 4 1 3 5 2 4 5 1 3 2 3 表头向量 1 3 5 例： 2 1 2 3 表头向量 2 1 3 图的邻接表表示 4. 邻接表的类型定义： 19 #0 /下一条边的顶点编号 /带权图的权值域 * /顶点编号 /指向第一条边的指针 /顶点和边的个数 对于 无向图，第 对于 有向图，第 要求入度，必须遍历整个邻接表。在单链表中，其邻接点域的值为 对于有向图，有时候就要建立一个你邻接表。即队每个顶点 样，逆邻接表第 20 5. 计算 图的度 例：图 51的邻接表和逆邻接表见 点形式： 21 6. 带权图邻接表。 值域：用于存储边的权值 画出 图 5 图 5邻接表。 （见黑板） 建立有向图的邻接表的方法： 将邻接表表头数组初始化 ; 第 i； 读入顶点对 ,产生一个表结点； 将 将该结点链到邻接表的表头数组的第 建立有向图的邻接表算法见 2 的遍历 遍历的含义及方法： 图的遍历 从图 序访问各顶点一次。 方法： 深度优先搜索法 广度优先搜索法 为克服顶点的重复访问，设立辅助数组 n。 1 顶点 0 顶点 i= 遍历方法 23 深度优先搜索法（ 一、过程 从图 G(V,E)中任一顶点 先访问 后访问 一未访问过的邻接点 以 直到所有顶点都被访问过。 二、例： 三、算法： 分析： a、为克服顶点的重复访问，设立一标志向量 n; b、图可用邻接矩阵或邻接表表示； c、 需 用到栈 。 从 4 2 5 意： 搜索到达某个顶点时 (图中仍有顶点未被访问 )，如果这个顶点的所有邻接点都被访问过，那么搜索就要回到前一个被访问过的顶点，再从该顶点的下一未被访问的邻接点开始深度优先搜索。； 深度搜索的顶点的访问序列不是唯一的。 24 连通图的深度优先搜索的算法 : g, v) 访问 v； v=1; / v初值都为 0，顶点 置为 1 找出 g中 w； w 未被访问 g,w); w=g中 25 深度优先搜索法算法： 对图按深度优先遍历的递归算法 （ 邻接表 ） ： =0 ; /*对访问标记 ( g , v ) /从第 g， 图以邻接表作为存储结构 *p ; “%d”,v ) ; /* 访问起始顶点 v*/ v = 1; /* 置 “ 已访问 ” 标记 */ p = v /* 取顶点表中 ( p != /* 依次搜索 ! p-) /*( g,p- ; /*沿此邻接点出发继续 p = p- /* 取 26 1 3 5 7 1 3 5 7 0 1 2 3 4 5 6 7 1 2 0 3 4 0 5 6 1 7 1 7 2 6 2 5 3 4 表头向量 深度优先搜索 : 27 深度优先搜索法算法： 对图按深度优先遍历的递归算法 （ 邻接矩阵 ） ： =0 ; /*对访问标记 ( g , v ) /从第 g， 图以邻接矩阵作为存储结构 j ; “%d”,v ) ; /* 访问起始顶点 v*/ v = 1; /* 置 “ 已访问 ” 标记 */ j=0;vj; /*顺序访问矩阵的第 （ m&!j） /*如果 v与 且 j 未被访问 */ g,j ) ; /*递归访问 j*/ 28 广度优先搜索法（ 一、过程 从图 G(V,E)中某一点 先访问 ， 然后再顺序访问 w1， ， 所有未被访问过的邻接点 ., 此过程直到所有顶点都被访问过。 二、例： 三、算法： 分析： a、为克服顶点的重复访问，设立一标志向量 n; b、图可用邻接矩阵或邻接表表示； c、顶点的处理次序 先进先出，故 需用到 一队列 从 4 2 5 9 广度优先遍历算法 基本思想： 未被访问 ” 标志； 同时置起始顶点 “ 已访问 ” 标记 ; 1） 取当前队头顶点； 2） 对与队头顶点相邻接的所有未被访问过 的顶点依次做： (a)访问该顶点； (b)置该顶点为 “ 已访问 ” 标记 ,并将它进队列； 3） 当前队头元素顶点出队； 4) 重复进行，直到队空时结束。 广度优先遍历算法： =0 ; /*对访问标记 N ; /*队列 对图按广度优先遍历的算法： g , v ) / 从顶点 按广度优先遍历图 g， 图用 邻接表 表示 %d”,v ); v = 1; /*访问初始顶点 ; ; v ; /* 起始顶点 （ 序号 ） 入队 */ /*队列不空 ， 则循环 */ )%N ; /*置队头 */ v= /* 队头元素出队 */ p=v*取刚出队顶点 ( p!= /* 依次搜索 ! p- /* “%d”,p- /*访问此邻接点 */ p-= 1 ; )%N ; /*队尾指针增 1*/ p-*访问过的顶点入队 */ p=p- /* 找 /* 31 1 3 5 7 1 3 5 7 0 1 2 3 4 5 6 7 1 2 0 3 4 0 5 6 1 7 1 7 2 6 2 5 3 4 表头向量 广度优先搜索 : g, v) ; /j; Q); %d”,v); /v=1; /访问过的标志 Q,v); ( !) /判队列是否为空 v=Q); Q); /出队列 j=0;vj; m & !j) /判断是否邻接点，且未被访问 %d”,j); j=1; /置被访问标志 Q,j); /邻接点入队列 32 33 1、判断图的连通性 对图 到一顶点集合，然后将之与 V(G)比较，若两集合相等，则图 则就说明有未访问过的顶点，因此图不连通。 图的连通分量 34 2、求图的连通分量 从无向图的每个连通分量的一个顶点出发遍历，则可求得无向图的所有连通分量。 图遍历的一种应用 算法： ) /*该图的连通分量 */ i; i=0; i,其中 三、最小生成树的构造方法（ 40 初态 5 0,1,2,3,4 1 5, 3 0, 1, 2, 4 2 5, 3, 2 0, 1, 4 3 5, 3, 2, 0 1, 4 4 5, 3, 2, 0, 1 4 5 5, 3, 2, 0, 1, 4 （ 6个顶点， 5条边） 0 1 3 2 4 5 2 5 1 3 5 4 6 6 5 6 步骤 已选顶点集 U 剩余顶点集 已选集 5 2 0 1 4 3 1 5 2 4 例：对下图用 最小生成树 41 最小生成树的构造方法（ 适合于求边稠密的带权图的最小生成树。 设 G=（ V， E）是个无向带权图， ) /*构造图 V ； U= p ； T= ； UV ） 在 pU ， qV p,q）； U=U+ q ; T=T+（ p,q） ; /* 具体类 见课本 本思想： =(V,E),令最小生成树初始状态为只有 =（ V， ），每个顶点自成一个连通分量； 中选取权值最小的边，若该边依附的顶点落在 将此边加入到则，舍去此边，选取下一条权值最小的边； 复 2，直至 42 四、最小生成树的构造方法 （ ） 43 初态 1 （ 2， 3） 5 接收 2 （ 2， 4） 6 接收 3 （ 3， 4） 6 不接收 4 （ 2， 6） 11 接收 5 （ 6， 4） 14 不接收 （构成回路） 6 （ 1， 2） 16 接收 7 （ 5， 4） 18 接收 （ 6个顶点， 5条边） 步骤 最小权边及权 动作 最小生成树 例：对下图用 造最小生成树 6 1 3 2 5 4 6 16 5 19 21 14 11 18 33 6 6 1 3 2 5 4 6 16 5 11 18 最小生成树 注： 用 权和相同。 44 最小生成树的构造方法（ 适合于求边稀疏的网的最小生成树。 原则： 按权值递增次序构造 即每次选权最小且不构成回路的边 ,直至 G ) /*构造图 ; V(T)=V(G); E(T)= ;/*( E(T)中边数 当且仅当 否则自己以自己为前提，不合理 ) 引出 如何检测 出现 拓扑排序 54 二、什么叫拓扑排序？ 定义：对 （ i, ,k, j, ） i是 i在 i、 径，则或 i在 k在 样的线性序列 称为 拓扑有序序列 。 定义：拓扑有序序列的构造过程称为 拓扑排序 。 55 三、拓扑排序方法 过程： (1)在 (2)从 重复 (1)、 (2)直至没有无前趋的顶点为止。 结果： 此图中无回 路，且得到拓扑