数据结构图.ppt

《数据结构图.ppt》由会员分享，可在线阅读，更多相关《数据结构图.ppt（39页珍藏版）》请在第壹文秘上搜索。

1、1图：要求 图的基本概念 图的存储 邻接矩阵、邻接表，邻接多重表，十字链表，边表） 图的遍历（深度优先遍历和广度优先遍历） 最小生成树 构造 拓扑排序和关键路径 拓扑排序算法实现 关键路径的求解步骤 最短路径 Dijkstra算法求一个顶点到其他各顶点的最短路径 Floyd算法：用来求各顶点之间的最短路径，时间复杂度为O(n3)2第一部分 图的定义和术语3 通常：用通常：用 |V| 表示顶点的数量（表示顶点的数量（|V| 1），），用用 |E| 表示边的数量（表示边的数量（|E| 0）。）。3/15“图图” G可以表示为两个集合：可以表示为两个集合：G =（V, E）。每条。每条边是一个顶点对

2、边是一个顶点对（v, w） E ，并且并且 v, w V。 图图的定义的定义(1) 无向图（完全有向图边数与顶点数之间的无向图（完全有向图边数与顶点数之间的 关系）关系）(2) 有向图（完全有向图有向图（完全有向图弧数与顶点数之间的弧数与顶点数之间的 关系关系）(3) 简单图简单图：没有重边和自回路的图没有重边和自回路的图(4) 邻接邻接(5) 路径，路径长度路径，路径长度(6) 无环（有向）图：没有任何回路的（有向）图无环（有向）图：没有任何回路的（有向）图(7) 度，入度，出度度，入度，出度(8) 无向图的顶点无向图的顶点连通、连通图、连通分量连通、连通图、连通分量(9) 有向图的顶点强连

3、通，有向图的顶点强连通，强连通图、连通分量强连通图、连通分量4邻接矩阵邻接矩阵（Adjacency Matrix）边边的信息：用的信息：用邻接矩阵邻接矩阵A n n （二维数组）表示为（二维数组）表示为: 其它的边或如果 0, ),( 1A Gvvvvjijiji顶点顶点信息：有信息：有n个顶点的图个顶点的图G(V, E) 用一维数组用一维数组D n 表示；表示；12/15 无权图的邻接矩阵定义无权图的邻接矩阵定义3V0V3V2V1 无权图的邻接矩阵表示示例无权图的邻接矩阵表示示例 图的存储结构图的存储结构 图的常用的存储结构有：图的常用的存储结构有：邻接矩阵、邻接链表邻接矩阵、邻接链表、十字

4、链表、邻接多重表和边表十字链表、邻接多重表和边表。5 ( ,) ,A ijijijwv vv vGij如果或的边其它 图的邻接矩阵表示示例图的邻接矩阵表示示例例例6.9带权图的邻接矩阵表示示例带权图的邻接矩阵表示示例12/15 带权图的邻接矩阵的定义带权图的邻接矩阵的定义6邻接表邻接表(Adjacency List) 对于图对于图G中的每个顶点中的每个顶点vi，将所有邻接于，将所有邻接于vi的顶点的顶点vj链成一链成一个单链表，这个单链表就称为顶点个单链表，这个单链表就称为顶点vi的邻接表，再将所有点的邻接表，再将所有点的邻接表表头放到一个数组中，就构成了图的的邻接表表头放到一个数组中，就构成

5、了图的邻接表邻接表。VertexFirstEdge顶点域顶点域 边表头指针边表头指针 AdjV Next邻接点域邻接点域 指针域指针域14/15Vertex：数据域，存储数据域，存储顶点顶点信息；信息；FirstEdge：指针域，指向链表中的：指针域，指向链表中的第一个第一个结点（即该顶点的结点（即该顶点的第一个第一个邻接点）。邻接点）。AdjV: : 邻接点域，指示与顶点邻接点域，指示与顶点Vi邻接的顶点在邻接的顶点在顶点表顶点表中的下标；中的下标；Next：链域，指向下一个与顶点：链域，指向下一个与顶点Vi邻接的邻接的结点结点。7邻接表邻接表(Adjacency List) 无向图的邻接表

6、表示示例无向图的邻接表表示示例3V0V3V2V114/158邻接表与逆邻接表邻接表与逆邻接表无向图无向图中有中有n 个顶点和个顶点和e条边，则它的邻接表需条边，则它的邻接表需n个头结点和个头结点和2e个表个表边结点。显然，在边边结点。显然，在边稀疏稀疏 ( e n(n-1)/2 ) 的情况下，用的情况下，用邻接表表示邻接表表示图比邻接矩阵节省存储空间图比邻接矩阵节省存储空间； 无向图的邻接表，顶点无向图的邻接表，顶点vi的度恰为第的度恰为第i个链表中的结点数；而在个链表中的结点数；而在有向有向图中图中，第，第i个链表中的结点个数只是顶点个链表中的结点个数只是顶点vi的出度，为便于确定顶点的出度

7、，为便于确定顶点vi的入度，可以建立一个有向图的的入度，可以建立一个有向图的逆邻接表逆邻接表，即对每个顶点，即对每个顶点vi 建立一个建立一个链接以链接以vi为头的弧的链表。为头的弧的链表。 例如：例如：15/159 对于有向图来说，邻接表有缺陷：对于有向图来说，邻接表有缺陷： 正邻接表求顶点的出度易，但求其入度难；正邻接表求顶点的出度易，但求其入度难； 逆邻接表求入度易，但求出度难。逆邻接表求入度易，但求出度难。 是否可以将两者结合？是否可以将两者结合？ 可以，可以，十字链表十字链表 对于对于无向图无向图来说，邻接表有缺陷：来说，邻接表有缺陷： 一条边一条边(v,w)的两个表结点分别被选在以

8、的两个表结点分别被选在以v和和w为头结点的链表中，在为头结点的链表中，在涉及到边的操作会带来不便涉及到边的操作会带来不便 改进？改进？ 邻接多重表邻接多重表(Adjacency Multilist)10 在某些应用中，有时主要考察图中边的权值以及所依附的在某些应用中，有时主要考察图中边的权值以及所依附的两个顶点，即两个顶点，即图的结构主要由边来表示图的结构主要由边来表示，称为，称为边表存储结边表存储结构构。 边表结构采用顺序存储，用边表结构采用顺序存储，用2个一维数组个一维数组构成，一个存储构成，一个存储顶点信息顶点信息，一个存储，一个存储边的信息边的信息。边数组边数组的每个元素由三部的每个元

9、素由三部分组成分组成：边的起点下标边的起点下标边的终点下标边的终点下标 边的权值边的权值边表边表11如图所示。如图所示。无向图的边表表示无向图的边表表示v0v2v4v3v16742398顶点表顶点表v0v1v2v3v401234边边 表表1 3 21 4 92 3 82 4 33 4 40 2 70 1 612例如：例如：1.一个具有8个顶点的有向图中，所有顶点的入度之和与所有顶点的出度之和的差等于（ ） A、16 B、4 C、0 D、22、一个n个顶点的连通无向图，其边个数至少为（ ） A、n-1 B、n C、n+1 D、nlogn答案：答案： C答案：答案： A3、十字链表适用于（ ） A

10、、完全图 B、连通分量 C、无向图 D、有向图答案：答案： D4、下列四种图的存储形式中，（ ）是用于无向图，并且边表中的边结点只需存放一次，可节约内存。A、邻接矩阵 B、邻接表C、十字链表 D、邻接多重表答案：答案： D5、在一个无向图中，所有顶点的度之和等于边数的( )倍。A 1/2 B 1 C 2 D 4答案：答案： C136、对于下面的带权无向图，请完成下列任务： （1）写出邻接矩阵 （2）画出最小生成树可以看出，如果是有向图，该图共有 4 条弧，如果是无向图，共有 2 条边。7、从邻接矩阵14第二部分 图的遍历15 深度优先搜索深度优先搜索（Depth First Search，简称

11、，简称DFS ） DFS类似于树的先序遍历；类似于树的先序遍历；3/12算法思想算法思想设初始状态时图中的所有顶点未被访问，则：设初始状态时图中的所有顶点未被访问，则： ：从图中某个顶点从图中某个顶点vi出发出发，访问，访问vi；然后找到然后找到vi的的一个邻接一个邻接顶点顶点vi1 ；：从从vi1出发，出发，深度优先搜索深度优先搜索访问和访问和vi1相相邻接且未被访问的邻接且未被访问的所有顶点；所有顶点；(3)(3)：转：转 ，直到和，直到和vi相相邻接的所有顶点都被访问为止邻接的所有顶点都被访问为止 (4)(4)：继续选取图中未被访问顶点：继续选取图中未被访问顶点vj作为起始顶点，转作为起

12、始顶点，转(1)，直，直到图中所有顶点都被访问为止。到图中所有顶点都被访问为止。16CDBAHGEF12345678【例例】一个无向图的一个无向图的DFS（也可以用于有向图也可以用于有向图）E A B C D F G H3/12 采用采用邻接表邻接表作为存储结构遍历时，找邻接点所需的时间取决于顶点和边的数量，作为存储结构遍历时，找邻接点所需的时间取决于顶点和边的数量，总时间复杂度为总时间复杂度为O(|V|+|E|) 。 采用采用邻接矩阵邻接矩阵作为存储结构遍历时，由于邻接矩阵是二维数组，要查找每作为存储结构遍历时，由于邻接矩阵是二维数组，要查找每个顶点的邻接点需要访问矩阵中的所有元素，因此时间

13、复杂度是个顶点的邻接点需要访问矩阵中的所有元素，因此时间复杂度是O(|V|2) 。所以：对于所以：对于点多边少点多边少的稀疏图来说，采用的稀疏图来说，采用邻接表邻接表 结构使得算法在时间效结构使得算法在时间效率上大大提高。率上大大提高。17 广广度优先搜索（度优先搜索（Breadth First Search，简称，简称BFS ） BFS类似于树的层序遍历；类似于树的层序遍历； 用一个数组用于标志已访问与否，还用一个数组用于标志已访问与否，还需要一个需要一个工作队列。工作队列。CDBAHGEF【例例】一个无向图的一个无向图的BFSE A F H B D G C12586374工作队列工作队列:

14、5/1218 算法思想算法思想 设初始状态时图中的所有顶点未被访问，则：设初始状态时图中的所有顶点未被访问，则： 从图中某个顶点从图中某个顶点vi出发出发，访问，访问vi；访问访问所有所有与与vi相相邻接且未被访问的所有顶点邻接且未被访问的所有顶点vi1, ,vi2, , ,vim;以以vi1, ,vi2, , ,vim的次序的次序，以，以vij(1jm)依次作为依次作为vi ，转，转； 继续选取图中继续选取图中未被访问未被访问顶点顶点vk作为起始顶点作为起始顶点，转，转，直到图中所有顶，直到图中所有顶点都被访问为止。点都被访问为止。 19 广度优先搜索算法广度优先搜索算法和和深度优先搜索算法

15、深度优先搜索算法在时间复杂度上是一样的：在时间复杂度上是一样的： 采用采用邻接矩阵邻接矩阵作为存储结构遍历时，时间复杂度是作为存储结构遍历时，时间复杂度是O(|V|2) 。 采用采用邻接表邻接表作为存储结构遍历时，时间复杂度为作为存储结构遍历时，时间复杂度为O(|V|+|E|) 。 不同之处仅仅在于顶点不同之处仅仅在于顶点访问次序不同访问次序不同。 基于基于图的遍历可以求图的遍历可以求 连通分量连通分量 生成树（广度优先生成树，深度优先生成树）生成树（广度优先生成树，深度优先生成树）20例如例如1、 有向图G=（V，E），V=1,2,3,4,5,6，E=,，以顶点1为出发点对图进行深度优先搜索

16、，得到的结点序列将可能为 1-2-5-4-3-6 或 1-3-6-5-4-2 。21第三部分 最小生成树22 生成树生成树（Spanning Tree）7/12CDBAHGEF由深度优先遍历由深度优先遍历DFS算法和广度优先遍历算法和广度优先遍历BFS算法都可以得到生成算法都可以得到生成树：如图所示（当有多个未访问邻接点可选时，以字母序策略选择）树：如图所示（当有多个未访问邻接点可选时，以字母序策略选择）生成树的顶点个数与图的顶点个数相同生成树的顶点个数与图的顶点个数相同生成树是图的生成树是图的极小极小连通子图连通子图（少于少于n-1条边就不条边就不连通连通）一个有一个有n个顶点的连通图的生成树有个顶点的连通图的生成树有n-1条边条边注意：注意：含含n个顶点个顶点n-1条边的图不一定是生成树条边的图不一定是生成树23 最小生成树（最小生成树（Minimum Spanning Tree，简记为，简记为MST）：）：带权连通图中代价（生成树中所有边的权值之和）最小的生成树。 构造最小生成树的算法有许多，最经典的有两种：普里姆普里姆( (Prim) )算法算法克鲁斯卡尔克鲁斯卡尔( (Kru