DS08_图.ppt

图的定义和术语 图的存储结构 图的遍历与连通性 最小生成树 活动网络 最短路径 8.1 图的定义和术语 8.1.1 图形结构的形式定义 图是由顶点集合(v)及顶点间的关系集合(R)组成的一种数据结构： Graph＝( V, R ) 其中： V = { x | x ? 某个数据对象} ， 是顶点的有穷非空集合； R——边的有限集合 R = {(x, y) | x, y ? V } 无向图 或 R = {x, y | x, y ? V Path (x, y)}有向图 是顶点之间关系的有穷集合，也叫做边(edge)集合。Path (x, y)表示从 x 到 y 的一条单向通路, 它是有方向的。x弧尾，y弧头 有向图与无向图 有向图中：边用x, y表示，且x与y是有序的。 a. 有向图中的边称为“弧” b. x——弧尾或初始点 y——弧头或终端点 无向图：边用(x, y) 表示，且顶x与 y是无序的。 完全图 在具有n 个顶点的有向图中，最大弧数为 n(n-1) 在具有n 个顶点的无向图中，最大边数为 n(n-1)/2 顶点的度 无向图：与该顶点相关联的边的数目 有向图： 入度ID(v) ：以该顶点为弧头的弧的数目 出度OD(v) ：以该顶点为弧尾的弧的数目 11、权和网权 某些图的边具有与它相关的数, 称之为权。这种带权图叫做网络。 8.1.3 图的运算概述 1、locvertex(G,v) 确定v在G中的位置2、getvertex(G,i) 求G中第i个顶点3、fistadj(G,v) 求G中v 的一个邻接点 4、nextadj(G,v,w) 求G 中v的下一个邻接点w …… 8.2 图的存储表示 顶点表: 一个记录各个顶点信息的一维数组， 邻接矩阵：一个表示各个顶点之间的关系（边或弧）的二维数组。 设图 G = (V, E)是一个有 n 个顶点的图，则图的邻接矩阵A[n][n] 定义为： 1 若Vi, Vj 或(Vi, Vj) ∈E A[i][j]= 0 反之 说明: 带权图的边结点中weight保存该边上的权值 。 顶点 Vi 的边链表的头结点存放在下标为 i 的顶点数组head[i]中。 在邻接表的边链表中，各个边结点的链入顺序任意，视边结点输入次序而定。 设图中有 n 个顶点，e 条边，则用邻接表表示无向图时，需要 n 个顶点结点，2e 个边结点；用邻接表表示有向图时，只需 n 个顶点结点，e 个边结点。 建立邻接表的时间复杂度为O(n*e)。若顶点信息即为顶点的下标，则时间复杂度为O(n+e)。 例: 带权图 的邻接表 8.2.3 有向图的十字链表 (Orthogonal List)——有向图的另一种链式存储结构 可看作是将有向图的邻接表和逆邻接表结合的一种链表 8.3 图的遍历 8.3.1 图的遍历概念：1、遍历概念：从图中某一顶点出发访遍图中其余顶点，且使每个顶点仅被访问一次，就叫做图的遍历 (Traversing Graph)。 2、遍历中的回路及解决方法：在图的遍历过程中可能存在回路，因为图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。解决回路的方法： 为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组 visit [ ]，它的初始状态为 0，在图的遍历过程中，一旦某一个顶点 i 被访问，就立即让 visit [i] 为 1，防止它被多次访问。 3、遍历方法：两种遍历图的方法：深度优先有哪些信誉好的足球投注网站(DFS:Depth-frist Search)、广度优先有哪些信誉好的足球投注网站(BFS:Breadth-frist Search) 三、DFS 的算法及程序 （1）从图中的某个顶点V出发，访问之； （2）依次从顶点V的未被访问过的邻接点出发，深度优先遍历图，直到图中所有和顶点V 有路径相通的顶点都被访问到； （3）若此时图中尚有顶点未被访问到，则另选一个未被访问过的顶点作起始点，重复上述（1）（2）的操作，直到图中所有的顶点都被访问到为止。 算法分析 图中有 n 个顶点，e 条边。 如果用邻接表表示图，沿 head[v]. link 链可以找到某个顶点 v 的所有邻接顶点 w。由于总共有 2e 个边结点，所以扫描边的时间为O(e)。而且对所有顶点递归访问1次，所以遍历图的时间复杂性为O(n+e)。