DBS第十章s图.pptx

内容提要1 图的基本概念2 图的存储结构包括图的邻接矩阵表示和邻接表表示法及其实现3 图的遍历 深度优先和宽度优先遍历4 最小代价生成树 普里姆算法 牛牛文库文档分享 10 1图的基本概念 与线性表 树和集合不同 在图结构中 每个数据元素都可以与任何其它数据元素相关 图在许多方面都有所应用 课堂提要第10章图10 1图的基本概念10 2图的存储结构10 3图的遍历10 5最小代价生成树 牛牛文库文档分享 b a 的图表示 a 电路示例 图10 1电路示例及对应的图表示 牛牛文库文档分享 图 graph 是数据结构G V E 其中V G 是G中结点的有限非空集合 结点的偶对称为边 edge E G 是G中边的有限集合 图中的结点又称为顶点 vertex 10 1 1图的定义与术语 1 0 2 3 4 a 图G1 图中 V G1 0 1 2 3 4 E G1 0 1 0 2 0 4 1 2 2 3 2 4 3 4 牛牛文库文档分享 有向图 directedgraph 指图中代表边的偶对是有序的 用代表一条有向边 又称为弧 则u称为该边的始点 尾 v称为边的终点 头 无向图 undirectedgraph 指图中代表边的偶对是无序的在无向图中边 u v 和 v u 是同一条边 1 0 2 3 4 b 有向图G2 1 0 2 3 4 a 无向图G1 牛牛文库文档分享 1 0 2 3 4 1 0 2 3 4 a 无向图G1 b 有向图G2 图中V G1 V G2 0 1 2 3 4 E G1 0 1 0 2 0 4 1 2 2 3 2 4 3 4 E G2 牛牛文库文档分享 自回路 如果图中存在无向边 u u 或有向边 则称这样的边为自回路 多重图 指图中两个顶点间允许有多条相同的边 自回路和多重图的例子 牛牛文库文档分享 邻接 如果 u v 是无向图中的一条边 则称顶点u和v相邻接 并称边 u v 与顶点u和v相关联 例如 顶点1和2是相邻接的 完全图 如果一个图有最多的边数 称为完全图 无向完全图有n n 1 2条边 有向完全图有n n 1 条边 例如 左图是一个完全图 有6条边 无向完全图 如果是有向图中的一条边 则称顶点u邻接到v 称顶点v邻接自u 并称边与顶点u和v相关联 牛牛文库文档分享 子图 图G的一个子图是图G V E 其中V G V G E G E G 1 0 2 3 4 1 0 2 3 4 G1 G2 牛牛文库文档分享 路径 在无向图G中 一条从s到t的路径是存在一个顶点序列 s v1 v2 vk t 使得 s v1 v1 v2 vk t 都是图G中的边 对于有向图顶点序列s v1 v2 vk t 应使 都是图G中的边 路径长度 指路径上边的数目 简单路径 除起点和终点可以相同外 路径上其余顶点各不相同 回路 起点和终点相同的简单路径 0 1 2 3 0 1 2 3 4 2 0 0 1 2 3 4 0 都是路径 它们的路径长度分别为3 6 5 其中 0 1 2 3 和 0 1 2 3 4 0 是简单路径 0 1 2 3 4 0 又是回路 牛牛文库文档分享 无向图中如果两个顶点u和v之间存在一条路径 则称顶点u和v是连通的 否则是不连通的 连通图 无向图中如果任意两个顶点之间是连通的 连通分量 无向图的极大连通子图 0和3是连通的 实际上该图任意两个顶点都是连通的 故该图是连通图 牛牛文库文档分享 0和6是不连通的 该图是非连通图 但它存在两个连通分量 注意极大的含义 如果某个连通子图再加上一个顶点后 仍然是连通的 则它不是连通分量 3 牛牛文库文档分享 强连通图 有向图中如果任意两个顶点u和v之间 存在一条从u到v的路径 同时存在一条从v到u的路径 则称该有向图为强连通图 强连通分量 有向图的极大强连通子图 3 4 4 3 牛牛文库文档分享 例如左图中 顶点1 2度分别为2和4 右图中 顶点0的入度和出度分别为3和1 顶点0的度为4 顶点2的入度和出度分别为 顶点的度 与该顶点相关联的边的数目 入度 有向图中顶点v的入度指以v为头的弧的数目 出度 有向图中顶点v的出度指以v为尾的弧的数目 有向图中 顶点的度 入度 出度 牛牛文库文档分享 生成树 无向图的生成树是一个极小连通子图 它包含图中所有顶点 但只有足以构成一棵树的 n 1 条边 去掉一条就不连通 再加上一条边将构成回路 有向图的生成森林 是一个子图 由若干棵互不相交的有根有向树组成 包含图中所有的顶点 1 0 2 3 4 图G1的生成树 图G1 牛牛文库文档分享 有根有向树 是一个有向图 它恰有一个顶点的入度为0 其余顶点的入度为1 如果略去边的方向 处理成无向图后 则图是连通的 网 在图的每条边上加上一个数字称为权 也称代价 带权的图称为网 有向无环图 DAG图 不包含回路的有向图 自由树 不包含回路的连通图 牛牛文库文档分享 ADT10 1Graph 数据 顶点的非空集合V和边的集合E 每条边由V中顶点的偶对表示 运算 voidCreateGraph Graph g intn Tnoedge 后置条件 已构造一个只有n个结点 不包含任何边的有向图 BOOLAdd Graph g intu intv Tw 后置条件 向图中添加权值为w 若边上没有权 则w 0 的边 若插入成功 则函数返回TRUE 否则返回FALSE BOOLDelete Graph g intu intv 后置条件 从图中删除边 若删除成功 则函数返回TRUE 否则返回FALSE BOOLExist Graphg intu intv 后置条件 如果图中存在边 则函数返回TRUE 否则返回FALSE intVerticesGraphg 后置条件 函数返回图中顶点数目 牛牛文库文档分享 上面列出的只是图的最基本的运算 在以后的各小节中 我们将通过添加新运算 陆续扩充ADT10 1的图抽象数据类型 主要包括以下图运算 1 深度优先搜索图 voidDFS Graphg 2 宽度优先搜索图 voidBFS Graphg 3 拓扑排序 voidTopoSort Graphg 4 关键路径 voidCriticalPath Graphg 5 普里姆算法求最小代价生成树 voidPrim Graphg intk 6 克鲁斯卡尔算法求最小代价生成树 voidKruskal Graphg intedges 7 迪杰斯特拉算法求单源最短路径 voidDijkstra Graphg intk Td intp 8 弗洛伊德算法求所有顶点之间的最短路径 voidFloyd Graphg T d int path 牛牛文库文档分享 1 图的矩阵表示法及其实现2 图的邻接表表示法及其实现 10 2图的存储结构 10 2 1图的矩阵表示法 1 邻接矩阵 一个有n个顶点的图G V E 的邻接矩阵是一个n n的矩阵A A的每个元素是0或1 课堂提要第10章图10 1图的基本概念10 2图的存储结构10 3图的遍历10 5最小代价生成树 牛牛文库文档分享 设V 0 1 2 n 1 如果G是无向图 则A的元素定义为 如果G是有向图 则A的元素定义为 牛牛文库文档分享 如果G是带权的有向图 网 那么A中的元素定义如下 牛牛文库文档分享 图10 7图的邻接矩阵 牛牛文库文档分享 0 邻接矩阵 例如 0 如果G是有向图 则A的元素定义为 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 强连通分量 牛牛文库文档分享 1 邻接矩阵C语言定义 10 2 2图的邻接矩阵实现 typedefstructgraph TNoEdge 两结点间无边时的值 0或 intVertices 图中顶点数T A 指向存储邻接矩阵的二维数组的指针 Graph 牛牛文库文档分享 建立邻接矩阵 程序10 1 voidCreateGraph Graph g intn Tnoedge inti j g NoEdge noedge g Vertices n g A T malloc n sizeof T for i 0 iA i T malloc n sizeof T for j 0 jA i j noedge g A i i 0 a L O M M O L L 0 0 0 0 noedge noedge noedge noedge noedge noedge 牛牛文库文档分享 BOOLExist Graphg intu intv if un 1 v n 1 u v a u v noEdge returnfalse returntrue 3 边的搜索 插入和删除 判边是否存在 3 1是否有边 1 3是否有边 有边 无边 牛牛文库文档分享 BOOLAdd Graph g intu intv Tw intn g Vertices if un 1 v n 1 u v g A u v g NoEdge printf BadInput n returnFALSE g A u v w returnTRUE 边的插入 1 插入0 2边 牛牛文库文档分享 边的删除BOOLDelete Graph g intu intv intn g Vertices if un 1 v n 1 u v g A u v g NoEdge printf BadInput n returnFALSE g A u v g NoEdge returnTRUE 1 删除0 2边 牛牛文库文档分享 10 2 3邻接表表示法 要点 1 为图中每一个顶点建立一个单链表 2 顶点u的单链表中的每一个结点指示u的一个邻接点v 即代表一条边 u v 或顶点u的单链表记录了与u相邻接 邻接自u 的所有顶点 每个单链表相当于邻接矩阵的一行 它指示了该行中的非零的元素 0123 1 3 0 0 2 牛牛文库文档分享 3 边结点的结构 指示顶点u的一个邻接点 指向u的下一个边结点 边上的权值 u 1 3 v 0 2 牛牛文库文档分享 存放顶点的名称及其他信息 指向u的第一个边结点 u 1 3 v 0 2 4 每个单链表可设立一个存放顶点u的有关信息的表头结点 也称顶点结点 顶点结点存入一个一维数组 牛牛文库文档分享 0123 a 图G1的邻接表 牛牛文库文档分享 0123 1 3 0 0 2 b 图G2的邻接表 牛牛文库文档分享 typedefstructenode intAdjVex TW structenode NextArc ENode typedefstructgraph intVertices ENode A Graph 边结点的结构类型 图中的顶点数 牛牛文库文档分享 3 建立邻接表函数CreateGraph构造一个有n个顶点 但不包含边的有向图 由于图的顶点数事先并不知道 所以我们使用动态存储分配的一维指针数组 voidCreateGraph Graph g intn inti g Vertices n g A ENode malloc n sizeof ENode for i 0 iA i NULL 牛牛文库文档分享 搜索 插入或删除从顶点u发出的边 只在A u 所指向的单链表中操作 程序如下 3 边的搜索 插入和删除 3 2 0 1 2是否有边 搜索边的函数BOOLExist Graphg intu intv intn ENode p n g Vertices if un 1 returnFALSE for p g A u p 牛牛文库文档分享 插入边的函数BOOLAdd Graph g intu intv Tw intn ENode p n g Vertices if un 1 v n 1 u v Exist g u v printf BadInput n returnFALSE p NewENode v w g A u g A u p returnTRUE 1 3 0 p 3 插入邻接表中由指针A u 所指示的单链表的最前面 牛牛文库文档分享 ENode NewENode intvex Tweight ENode nextarc ENode p p ENode malloc sizeof ENode p AdjVex vex p W weight p NextArc nextarc returnp 牛牛文库文档分享 删除边的函数BOOLDelete Graph g intu intv intn g Vertices ENode p q if u 1 0123 1 3 0 P q NULL 在由指针A u 所指示的单链表中 搜索AdjVex域的值为v的边结点 牛牛文库文档分享 10 3图的遍历 图的遍历 指从图G的任意一个顶点v出发 访问图中所有结点且每个结点仅访问一次的过程 图遍历的方法 深度优先搜索 类似于树的先序遍历 和宽度优先搜索 类似于树的按层次遍历 课堂提要第10章图10 1图的基本概念10 2图的存储结构10 3图的遍历10 5最小代价生成树 牛牛文库文档分享 10 3 2深度优先遍历 图遍历与树遍历的差异 1 从图中任意一个顶点出发未必能到达其它所有顶点 2 图中存在回路时 又可能多次经过同一个顶点 为了避免发生上述两种情况 图的搜索算法通常为图的每个顶点保留一个标志位 markbit 算法开始时 所有顶点的标志位清零 在遍历过程中 当某个顶点被访问时 其标志位被标记 在搜索中遇到被标记过的顶点则不再访问它 搜索结束后 如果还有未标记过的顶点 遍历算法可以选一个未标记的顶点 从它出发开始继续搜索 牛牛文库文档分享 1 深度优先搜索算法 从图G中某个顶点v出发 深度优先搜索图的DFS算法如下 1 访问顶点v并打上标记 2 依次从v的未访问过的邻接点出发 深度优先搜索图G 牛牛文库文档分享 从A出发 将访问走过的边保留 去掉访问时未走过的边 就得到以A为根的DFS生成树 如果是连通的无向图或强连通的有向图 上述DFS算法必定可以系统地访问图中的全部顶点 一条无向边被视作两条有向边 被查看两次 牛牛文库文档分享 a 有向图G B F D E A C G 对有向图G 从A出发DFS 访问的次序是A B D C 遍历了所有从A出发可到达的顶点 即A的可达集 另选一个顶点出发搜索图G的其余部分 b 图G的邻接表 1 A B D C F G E 牛牛文库文档分享 a 有向图G B F D E A C G c 图G深度优先搜索的生成森林 思考 图的DFS序列是否惟一 指从同一顶点出发 A B D C F G E 图中所有顶点 以及在遍历时经过的边构成的子图 称为图的深度优先搜索生成树 dfsspanningtree 或生成森林 牛牛文库文档分享 DFS递归算法 程序10 5 voidDFS Graphg intv BOOL visited ENode w visited v TRUE printf d v for w g A v w w w NextArc if visited w AdjVex DFS g w AdjVex visited voidTraversal DFS Graphg BOOLvisited MaxSize inti n g Vertices for i 0 i n i visited i FALSE for i 0 i n i if visited i DFS g i visited 对V未标记的邻接点嵌套调用DFS函数 对尚未标记的顶点调用DFS函数 牛牛文库文档分享 3 时间分析 深度优先搜索算法对有向图的每条边只查看1次 而对于无向图 查看2次 n个顶点 e条边的图采用邻接表存储 DFS算法的时间为O n e 而采用邻接矩阵表示 时间为O n2 牛牛文库文档分享 10 3 3宽度优先遍历 从图中任一顶点v出发遍历图的BFS算法的描述 1访问顶点v并打上标记 2依次访问顶点v的未访问的邻接点 再访问与这些邻接点相邻接且未访问的顶点 3若图中还有顶点未被访问 则另选一个未访问的顶点 重新开始上述过程 1 宽度优先搜索 宽度优先搜索是一种分层的搜索过程 每向前走一步可能访问一批顶点 不像深度优先搜索那样有往回退的情况 因此 广度优先搜索不是一个递归的过程 其算法也不是递归的 牛牛文库文档分享 6 2 7 0 9 8 3 5 4 10 1 11 a 无向图G 例 对下图 从顶点0出发BFS遍历 其遍历序列是 0 1 11 10 2 5 6 9 3 4 7 8 0 1 11 10 2 5 6 9 3 4 7 8 图中顶点以及遍历时生成的边所构成的子图称为宽度优先搜索生成树 牛牛文库文档分享 2 0 5 10 1 11 a 无向图G 0 1 11 10 2 5 0 1 11 10 2 5 宽度优先搜索算法要实现按层次访问 需要一个队列来保存已访问过但其邻接点尚未考察的顶点 1 访问顶点v的所有未访问过的邻接点时 需将这些邻接点保存在队列中 2 当顶点v的所有邻接点全部访问完毕后 从队列中取出一个顶点 接着访问这个顶点的邻接点 并依次进队列 牛牛文库文档分享 2 BFS算法 采用邻接表作为图的存储结构 其宽度优先搜索的程序如下 include queue h voidBFS Graphg Tv BOOL visited ENode w Tu Queueq CreateQueue 入队 牛牛文库文档分享 while IsEmpty q QueueFront q u的邻接顶点入队 牛牛文库文档分享 voidTraversal BFS Graphg BOOLvisited MaxSize inti n g Vertices for i 0 i n i visited i FALSE for i 0 i n i if visited i BFS g i visited 牛牛文库文档分享 BFS算法的特点 1 每个顶点进出队列各一次 2 对于每个出队的顶点 都要检查其所有的邻接点 对于无向图每条边被检查2次 3 n个顶点 e条边的图采用邻接表存储 BFS算法的时间为O n e 而采用邻接矩阵表示 时间为O n2 如同二叉树的遍历算法 图的DFS和BFS算法是最重要 最基本的算法 许多有关图的算法都可以对它们稍加修改得到 例如 求无向图的连通分量 有向图的强连通分量 生成树 森林 等 牛牛文库文档分享 已知一有向图的邻接表存储结构如下图所示 请问 每个顶点的入度和出度 并给出从顶点1出发的深度优先遍历和宽度优先遍历序列 1 01234 ABCDE 3 1 3 3 2 4 ABCDE 出度 30202 ABCDE 入度 02131 A B C D E 顶点1出发的深度优先遍历 A C D E B 顶点1出发的宽度优先遍历 A C B D E 牛牛文库文档分享 10 4最小代价生成树 问题的引入 在n个城市之间架设通信线路 已知每两个城市间架设线路的代价 问如何选择n 1条线路 可以使总代价最小 10 4 1基本概念 0 1 3 2 3 5 1 2 7 8 构造一个连通图的最小代价生成树 牛牛文库文档分享 一个连通图的生成树是 1 一个极小连通子图 2 它包括图中全部顶点 3 有尽可能少的边 只有足以构成一棵树的n 1条边 一棵生成树的代价是各条边上的代价之和 一个网络的生成树中具有最小代价的生成树称为该网络的最小代价生成树 构造最小代价生成树的两种算法 普里姆算法 Prim 克鲁斯卡尔算法 Kruskal 牛牛文库文档分享 0 1 3 2 3 5 1 2 7 8 牛牛文库文档分享 设G V E 是带权的连通图 T V E 是正在构造中的生成树 初始状态下 这棵生成树只有一个顶点 没有边 即V u0 E u0是任意选定的起始顶点 从初始状态开始 重复执行下列运算 在所有u V v V V 的边 u v u v E中找一条代价最小的边 u v 边 u v 并入集合E 将顶点v 并入集合V 直到V V 为止 这时E 中必有n 1条边 T V E 是图G的一棵最小代价生成树 1 普里姆算法 Prim 10 4 2普里姆算法 u v 的含义是 一端在树上 另一端不在树上的最小权值边 牛牛文库文档分享 图10 15普里姆算法构造最小代价生成树的过程 0 3 1 2 4 5 3 6 6 6 5 5 5 4 2 1 图G 构造中的最小代价生成树T 普里姆算法演示 牛牛文库文档分享 2 实现普里姆算法 为实现Prim算法 定义两个一维数组 用于存放中间构造过程和最终结果 nearestlowcost 设v是当前尚未选入生成树的顶点 nearest v 中保存边 u v 在生成树上的那个顶点u 边 u v 是所有u V 的边中权值最小的边 u v u 1 0 3 8 7 6 5 5 V nearest v 牛牛文库文档分享 定义一个一维数组mark 用于表示某个顶点是否在生成树上 如果mark v false 表示v未加入生成树 反之 v已选入 初始时 nearest v 1 lowcost v MaxNum mark v FALSE nearest v v lowcost v 代表一条权值为lowcost v 两个顶点分别为nearest v 和v的一条边 nearest v v 如 2 1 5 边 2 1 的代价为5 其中nearest 1 2 lowcost 1 5它记录当前对v而言 与生成树上顶点相邻的所有边中权值最小者 牛牛文库文档分享 0 3 1 2 4 5 3 6 6 6 5 5 5 4 2 1 1 2 3 4 5 6 1 5 5 0 0 0 0 6 4 2 3 2 2 5 2