数据结构课件chapter7.ppt

计算机科学与工程系 计算机科学与工程系 第七章 图 图的基本概念 图的存储表示 图的遍历与连通性 最小生成树 最短路径 活动网络 7.1 图的基本概念 图的定义 图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构： Graph＝( V, E ) 其中 V = { x | x ? 某个数据对象} 是顶点的有穷非空集合； E = {(x, y) | x, y ? V } 或 E = {x, y | x, y ? V Path (x, y)} 是顶点之间关系的有穷集合，也叫做边(edge)集合。Path (x, y)表示从 x 到 y 的一条通路。 有向图与无向图 完全图 邻接顶点 如果 (u, v) 是 E(G) 中的一条边，则称 u 与 v 互为邻接顶点。 子图 设有两个图G＝(V, E)和G’＝(V’, E’), 若 V ’? V 且 E’ ?E, 则称 图G’ 是图G 的子图。 顶点的度 一个顶点v 的度是与它相关联的边的条数，记作TD(v)。 顶点 v 的入度 是以 v 为终点(弧头)的有向边的条数, 记作 ID(v); 顶点 v 的出度是以 v 为始点(弧尾)的有向边的条数, 记作 OD(v)。 路径 在图 G＝(V, E) 中, 若从顶点 vi 出发, 沿一些边经过一些顶点 vp1, vp2, …, vpm，到达顶点vj。则称顶点序列 ( vi vp1 vp2 ... vpm vj ) 为从顶点vi 到顶点 vj 的路径。它经过的边(vi, vp1)、(vp1, vp2)、...、(vpm, vj)应是属于E 的边。 路径长度 非带权图的路径长度是指此路径上边的条数。 带权图的路径长度是指路径上各边的权之和。 简单路径 若路径上各顶点 v1,v2,...,vm 均不互相重复, 则称这样的路径为简单路径。 回路 若路径上第一个顶点 v1 与最后一个顶点vm 重合, 则称这样的路径为回路或环。 简单回路 除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫简单回路 7.2 图的存储结构 1）存储特点 在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表； 还有一个表示各个顶点之间关系的邻接矩阵。 2）邻接矩阵 设图 A = (V, E)是一个有 n 个顶点的图，则图的邻接矩阵是一个二维数组 A[n][n]，定义： 网络的邻接矩阵 3）数据类型描述 4）图的创建 7.2.2 邻接表 (Adjacency List) 1) 存储特点 对于图G中的每个顶点vi，把所有邻接于vi的顶点vj链成一个单链表，这个单链表称为顶点vi的邻接表； 将所有点的邻接表表头放到数组中，就构成了图的邻接表 特点 无向图中顶点Vi的度为第i个单链表中的结点数 有向图中 顶点Vi的出度为第i个单链表中的结点个数 顶点Vi的入度为整个单链表中邻接点域值是i的结点个数 逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表 2）数据类型描述 7.2.3 十字链表 (Orthogonal List) 十字链表是有向图的另一种链式存储结构，它实际上是邻接表与逆邻接表的结合 1) 存储特点 图中每一条弧有一个结点，把弧头相同的弧连在同一链表上,弧尾相同的弧也连在同一链表上。结点结构为： 顶点结点为链表头结点，其结构为： 7.2.4 邻接多重表(Adjacency Multilist) 邻接多重表是无向图的另一种链式存储结构 1) 存储特点 图中每一条边用一个边结点表示，其结构为： 每个顶点用一个结点表示，其结构为： 在邻接多重表中, 所有依附于同一个顶点的边都链接在同一个单链表中。 邻接多重表的结构 7.3 图的遍历与连通性 从图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，叫做图的遍历 ( Graph Traversal )。 为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组 visited [ ]，它的初始状态为 0，在图的遍历过程中，一旦某一个顶点 i 被访问，就立即让 visited [i] 为 1，防止它被多次访问。 7.3.1 深度优先有哪些信誉好的足球投注网站DFS 1）基本思想： 任选图中一个顶点 v , 访问此顶点, 并作访问标记。 从 v 出发，访问它的任一未被访问过的邻接顶点 w ，作访问标记，并以 w 为新的出发点，继续进行深度优先有哪些信誉好的足球投注网站。 当某个顶点的所有邻接顶点都被访问过后，则退回到前一次刚访问过的顶点k，从k的另一个没有被访问的邻接顶点出发进行深度优先有哪些信誉好的足球投注网站。