-数据结构.pptVIP

第7章 图 7.1 图的定义和术语 一、图的定义 图是一个二元组，G=(V,E)。 其中， V：顶点的有限集, E：关系(边)的有限集。 二、图的特点 图是一种网状的数据结构，其中的结点之间的关 系是任意的，即图中任何两个结点之间都可能直接相 关。 三、术语 顶点：图中的数据元素。 边：两个顶点之间的关系。 对于无向图，图中的顶点偶对（边）是无序的； 而对于有向图，图中的顶点偶对（弧）是有序的。 完全图：有n(n-1)/2条边的无向图（如图G1)。 有向完全图：有n(n-1)条边的有向图(如图G4)。 稠密图：有很少的边或弧的图。 稀疏图：有很多的边或弧的图。 子图：设两个图G＝(V, E)和G’=(V’,E’)，如果V’?V且 E’ ?E，则称G’为G的子图。 权(Weight)：与图的边相关的数值。 网（Network)：带权的图。 邻接点： 对于无向图G＝(V,E)，若存在顶点对(x,y)?E， 则称顶点x和y互为邻接顶点。即x和y相邻接（相 关联）。 对于有向图G＝(V,E)，若存在顶点对x,y?E， 则称顶点x邻接到顶点y，顶点y邻接于到顶点x。 顶点的度 在无向图中，和该顶点相关联的边的数目称为顶 点的度。 例：TD(v1)=3, TD(v2)=2 顶点的度 在有向图中，若x,y是一条弧，以x为尾的弧的 数目称为顶点x的出度;以x为头的弧的数目称为顶点x 的入度。 顶点的度等于该顶点的入度与出度之和。 7.2.3 十字链表 7.2.4 邻接多重表 7.4 最小生成树 二、prim方法 二、prim方法 二、prim方法 二、prim方法 二、prim方法 二、prim方法 图的遍历：从图中某一顶点出发访遍图中其余结点，使每一个结点被访问且仅被访问一次。 图的遍历算法是求解图的连通性问题、拓扑问题和求关键路径等算法的基础。 图的遍历通常有两种方法：深度优先有哪些信誉好的足球投注网站和广度优先有哪些信誉好的足球投注网站。它们对有向图和无向图都适用。 7.3 图的遍历 类似于树的先根遍历，是树的先根遍历的推广。 从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图, 直至所有与v有通路的顶点都被访问到；若此时图中还有顶点未被访问到，则另选图中未被访问的顶点作起点，重复上述过程，直到图中所有顶点都被访问到为止。 7.3.1 深度优先有哪些信誉好的足球投注网站(Depth First Search) 深度优先遍历序列： v1,v2,v4,v8,v5,v3,v6,v7 深度优先序列： V1,V2,V5,V8,V4,V3,V6,V7 V1,V2,V5,V8,V4,V3,V7,V6 V1,V3,V6,V7,V2,V4,V8,V5 V1,V3,V7,V6,V2,V4,V8,V5 V1,V3,V7,V6,V2,V5,V8,V4 V2,V4,V8,V5,V1,V3,V6,V7 V2,V5,V8,V4,V1,V3,V6,V7 V2,V5,V8,V4,V1,V3,V7,V6 V2,V1,V3,V6,V7,V4,V8,V5 V2,V1,V3,V6,V7,V5,V8,V4 V2,V1,V3,V7,V6,V4,V8,V5 V2,V1,V3,V7,V6,V5,V8,V4 A B C D E F G I J L H M K F G I J L K 无向图G的三个连通分量 无向图G 深度优先有哪些信誉好的足球投注网站森林 A B C D E H M 深度优先有哪些信誉好的足球投注网站森林 A B C D E H M F G I J L K void dfs (graph g, vtxptr v0){ //从v0出发深度优先遍历图g, // g是连通图 或 非连通图中的一个连通分量 访问v0; w=v0的第一个邻接点； while (当邻结点w存在时) { if （w未访） dfs(g,w); //若W未访问，则深度优先遍历图 w=下一邻接点； } }// dfs void dfstraverse (graph g){ //深度优先遍历图g, for (v=1;v=n;v++) mark[v]=0; for (v=1;v=n;v++) if (!mark[v]) //mark[v]==0