第5章图-35.ppt

第5章 图 张成文 北京邮电大学计算机学院 本章不予讨论的图 小结 图是一种复杂的非线性结构，具有广泛的应用背景。本章涉及到的基本概念有： 图：由两个集合V和E组成，记为G＝(V，E)，其中v是顶点的有穷非空集合，E是V中顶点偶对（称为边）的有穷集。通常，也将图G的顶点集和边集分别记为V(G)和E(G)。E(G)可以是空集，若E(G)为空，则图G只有顶点而没有边，称为空图。 有向图（Digraph）：若图G中的每条边都是有方向的，则称G为有向图。 无向图（Undigraph）：若图G中的每条边都是没有方向的，则称G为无向图。 邻接点(Adjacent)：若(vi，vj)是一条无向边，则称顶点vi和vj互为邻接点。 度(Degree)：无向图中顶点v的度是关联于该顶点的边的数目。 入度(indegree)：若G为有向图，则把以顶点v为终点的边的数目，称为v的入度，记为ID(v)。 出度(outdegree)：把以顶点v为始点的边的数目，称为v的出度，记为OD(v)。 子图(Subgraph)：设G＝(V，E)是一个图，若v′是v的子集，E′是E的子集，且E′中的边所关联的顶点均在v′中，则G′＝(V′，E′)也是一个图，并称其为G的子图。 路径(Path)：在无向图G中，若存在一个顶点序列vp,vi1,vi2…，vin，vq，使得(vp，vil)，(vi1,vi2)，…，(vin，vq)均属于E(G)，则称顶点vp到vq存在一条路径。 路径长度：该路径上边的数目。 简单路径：若一条路径上除了vp和vq可以相同外，其余顶点均不相同，则称此路径为一条简单路径。 简单回路或简单环(Cycle)：起点和终点相同(vp＝vq)的简单路径称为简单回路或简单环。 二、广度优先有哪些信誉好的足球投注网站 V w1 w8 w3 w7 w6 w2 w5 w4 对连通图,从起始点V到其余各顶点必定存在路径。 其中，V-w1, V-w2, V-w8 的路径长度为1； V-w7, V-w3, V-w5 的路径长度为2； V-w6, V-w4 的路径长度为3。 w1 V w2 w7 w6 w3 w8 w5 w4 从图中的某个顶点V0出发,并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。 若此时图中尚有顶点未被访问, 则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。 void bfs(graph g, vtxptr v0){ visite(v0); visited[v0] =true; initq (q); enqueue(q,v0); //v0入队列q while (!empty(q)) { v =dlqueue(q); //队头出队赋给v w =firstadj(g, v); //w为v第一邻接点 while (w0) //当邻接点存在 { if (!visited[w]) { visite(w); visited[w] =true; enqueue(q, w); } //w入队列 w=nextadj(g,v,w); //下一邻接点 } } } F F F F F F F F F V0 w1 w8 w3 w7 w6 w2 w5 w4 w1 V0 w2 w7 w6 w3 w8 w5 w4 v0 w1 w2 w8 w7 w3 w5 w6 w4 v0 w1 w2 w8 w7 w3 w5 w6 w4 visited enqueue T T T T T T T T T * * * 主要内容 5.1 图的定义与术语 5.2 图的存储表示 5.3 图的遍历 　1. 熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系。 　2. 熟练掌握图的两种有哪些信誉好的足球投注网站路径的遍历：遍历的逻辑定义、深度优先有哪些信誉好的足球投注网站和广度优先有哪些信誉好的足球投注网站的算法。 本章要点 有向图是由顶点集 V 和弧集 R构成的数据结构。 Graph = (V , R ) 其中: V={v|v∈data object} R={VR} VR={v,w| (v,w∈V)} v,w表示从 v 到 w 的一条弧，并称 v 为弧尾，w 为弧头。 5.1 图的定义与术语 由于“弧”是有方向的，因此称由顶点集和弧集构成的图为有向图。 例如: G1 = (V1,