数据结构与算法分析6.ppt

《数据结构与算法分析6.ppt》由会员分享，可在线阅读，更多相关《数据结构与算法分析6.ppt（18页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、 第第6 6章章 图图 6.1 图的基本概念 6.2 图的存储结构 6.3 图的遍历 6.4 最小生成树6.5 最短路径和拓扑 排序 6.1 6.1 图的基本概念图的基本概念 6.1.1 6.1.1 图的定义图的定义 图的定义:图可用二元组表示：Graph=(V，E)，其中V表示元素（顶点）的非空有限集合；E表示元素之间关系（边）的有限集集合，边是顶点偶对。可以看出图的每个结点有任意多个前驱和后继结点。有向图和无向图 子图6.1 6.1 图的基本概念图的基本概念6.1.2 6.1.2 常用术语常用术语完全图完全图 ：在一个有在一个有n个顶点的无向图中，若每个顶点到个顶点的无向图中，若每个顶点到

2、其它（其它（n-1）顶点都有一条边，则图中有顶点都有一条边，则图中有n个顶点且有个顶点且有（n*（n-1）/2）条边的图称为无向完全图条边的图称为无向完全图 邻接点邻接点 ：对无向图对无向图G=（V，E），），若有（若有（V1，V2）E，则称则称V1和和V2互为邻接点互为邻接点 相关边：两个相邻接的点连成的边叫做这两个结点的相相关边：两个相邻接的点连成的边叫做这两个结点的相关边关边度：与每个顶点相连的边的数叫该点的度度：与每个顶点相连的边的数叫该点的度入度入度 ：对有向图中某结点的孤头数（边的终点）称为该：对有向图中某结点的孤头数（边的终点）称为该结点的入度结点的入度6.1 6.1 图的基本概

3、念图的基本概念出度出度 ：对有向图中某结点的孤尾数（边的终点）称为该：对有向图中某结点的孤尾数（边的终点）称为该结点的出度结点的出度 路径路径 ：在一图中若从某个顶点：在一图中若从某个顶点V VP P出发，沿着一些边经过出发，沿着一些边经过顶点顶点V V1 1，V V2 2，V Vm m到达到达V Vg g则称顶点序列（则称顶点序列（V VP P，V V1 1，V V2 2，V Vm m，V Vg g)为从为从V Vp p到到V Vg g的路径的路径 回路回路 ：从一顶点出发又回到该顶点，则所经过的路径称：从一顶点出发又回到该顶点，则所经过的路径称为回路为回路 连通：在无向图中，若从顶点连通：

4、在无向图中，若从顶点Vi到顶点到顶点Vj之间有路径则之间有路径则称这两个顶点是连通的称这两个顶点是连通的 权：有些图对应每条边有一相应的数值，这个数值称为权：有些图对应每条边有一相应的数值，这个数值称为该边的权该边的权 网：带权的图称为网网：带权的图称为网 6.2 6.2 图的存储结构图的存储结构 6.2.1 6.2.1 邻接矩阵表示法邻接矩阵表示法 邻接矩阵是：设G=（V,E）是具有n个顶点的图，则G的邻接矩阵是一个n*n的方阵，其中矩阵每一行分别对应图的各个顶点；矩阵的每一列分别对应图的各个顶点邻接矩阵的性质：1图中各顶点序号确定后，图的邻接矩阵是唯一确定的；2无向图和无向网的邻接矩阵是一

5、个对称矩阵；3无向图邻接矩阵中第i行（或第i列）的非0元素的个数即为第i个顶点的度；4有向图邻接矩阵第i行非0元素个数为第i个顶点的出度，第i列非0元素个数为第i个顶点的入度，第i个顶点的度为第i行与第i列非0元素个数之和；5无向图的边数等于邻接矩阵中非0元素个数之和的一半，有向图的弧数等于邻接矩阵中非0元素个数之和 6.2 6.2 图的存储结构图的存储结构6.2.2 6.2.2 邻接表表示法邻接表表示法 在邻接表表示法中，用一个顺序存储区来存储图中各顶点的数据，并对图中每上顶点vi建立一个单链表（此单链表称之为的vi邻接表），把顶点vi的所有相邻顶点，即其后继顶点的序号链接起来 邻接表与邻接

6、矩阵的关系：1对应于邻接矩阵的每一行有一个线形链接表；2链接表的表头对应着邻接矩阵该行的顶点；3链接表中的每个结点对应着邻接矩阵中该行的一个非零元素；4对于无向图：一个非零元素表示与该行顶点相邻接的另一个顶点；5对于有向图：非零元素则表示该行顶点为起点的一条边的终点。6.2 6.2 图的存储结构图的存储结构邻接表的性质：1图的邻接表表示不是唯一的，它与表结点的链入次序有关；2无向图的邻接表中第i个边表的结点个数即为第i个顶点的度；3有向图的邻接表中第i个出边表的结点个数即为第i个结点的出度，有向图的逆邻接表中第i个入边表的结点个数即为第i个结点的入度；4无向图的边数等于邻接表中边表结点数的一半

7、，有向图的弧数等于邻接表（逆邻接表）中出边表结点（入边表结点）的数目。6.2 6.2 图的存储结构图的存储结构6.2.3 6.2.3 关联矩阵关联矩阵 图的另一种矩阵表示法为以顶点和边的关联关系为基础建立矩阵，这个矩阵称之为关联矩阵定义如下：图G=（V,E）的关联矩阵是一个矩阵，使得 6.3 6.3 图的遍历图的遍历 6.3.1 6.3.1 深度优先搜索遍历深度优先搜索遍历 从图中某个顶点出发访问图中所有顶点，且使得每一顶点仅被访问一次，这一过程称之为图的遍历 假定给定图G的初态是所有顶点均未曾访问过，在G中任选一顶点v为初始出发点，则深度优先搜索可定义如下：从指定的起点v出发(先访问v，并将

8、其标记为已访问过)，访问它的任意相邻接的顶点w1，再访问w1的任一个未访问的相邻接顶点w2，如此下去，直到某顶点已无被访问过的邻接顶点或者它的所有邻接顶点都已经被访问过了，就回溯到它的前驱。如果这个访问和回溯过程返回到遍历开始的顶点，就结束遍历过程。如果图中仍存在一些未访问过的结点，就另选一个未访问过的结点重新开始深度优先搜索遍历。6.3 6.3 图的遍历图的遍历深度优先搜索遍历算法表示如下：DFS(v)num(v)=i+;for所有与v邻接的顶点uifnum（u）是0将edge（uv）连接到edges中；DFS（u）；depthFirstSearch()for所有向量vnum(v)=0;ed

9、ges=null;i=1;while有一个向量v使得num(v)是0DFS（v）；输出edges;6.3 6.3 图的遍历图的遍历6.3.2 6.3.2 广度优先搜索遍历广度优先搜索遍历设图设图G G的初态是所有顶点均未访问过，在的初态是所有顶点均未访问过，在G G中任选中任选一顶点一顶点v v为初始出发点，则广度优先搜索遍历的为初始出发点，则广度优先搜索遍历的基本思想是：从指定的起点基本思想是：从指定的起点v v出发，访问与它相出发，访问与它相邻的所有顶点邻的所有顶点w w1 1，w w2 2，；然后再依次访问然后再依次访问w w1 1，w w2 2，邻接的尚未被访问的所有顶点，再从邻接的尚

10、未被访问的所有顶点，再从这些顶点出发访问与它们相邻接的尚未被访问的这些顶点出发访问与它们相邻接的尚未被访问的顶点，直到所有顶点均被访问过为止。如果图中顶点，直到所有顶点均被访问过为止。如果图中仍存在一些未访问过的结点，就另选一个未访问仍存在一些未访问过的结点，就另选一个未访问过的结点重新开始广度优先搜索遍历。过的结点重新开始广度优先搜索遍历。6.3 6.3 图的遍历图的遍历深度优先搜索遍历算法（以队列作为基本数据结构）表示如下：breadthFirstSearch()for所有顶点unum(u)=0；edges=null；i=l；while存在一个顶点v使得num(v)=0num(v)=i+；

11、enqueue(v)；/进入队列while队列非空v=dequeue()；for所有和v邻接的顶点uifnum(u)是0num(u)=i+；enqueue(u)；将edge(vu)连接到edges中；输出edges；6.4 6.4 最小生成树最小生成树 6.4.1 6.4.1 生成树生成树生成树生成树 ：一个连通图一个连通图G G的子图如果是一棵包含的子图如果是一棵包含G G的所有顶点的树，则的所有顶点的树，则该子图称为该子图称为G G的生成树的生成树 n n个顶点的连通图个顶点的连通图G G的任何生成树一定是包含的任何生成树一定是包含n n个顶点和个顶点和n-1n-1条边的连条边的连通子图（

12、称为通子图（称为G G的极小连通子图），反之亦然的极小连通子图），反之亦然 生成树具有以下特点生成树具有以下特点:1如果在生成树中去掉任何一条边，此子图就会变成非连通图；如果在生成树中去掉任何一条边，此子图就会变成非连通图；2任任意意两两个个顶顶点点之之间间有有且且仅仅有有一一条条路路径径，如如再再增增加加一一条条边边,就就会会出出现一条回路。现一条回路。3 3由遍历连通图由遍历连通图G G时所经过的边和顶点构成的子图是时所经过的边和顶点构成的子图是G G的生成树。的生成树。普里姆（Prim）算法 克鲁斯卡尔（Kruskal）算法 6.5 6.5 最短路径和拓扑排序最短路径和拓扑排序6.5.1

13、 6.5.1 最短路径最短路径 最短路径问题，即求两个顶点间长度最短的路径 路径长度不是指路径上边数的总和，而是指路径上各边的权值总和 单源路径最短问题是指：对于给定的有向网络G=(V,E)及单个源点v，求从v到G的其余各顶点的最短路径。6.5 6.5 最短路径和拓扑排序最短路径和拓扑排序迪卡斯特拉（Dijkstra）算法基本思想是：设置两个顶点集S和T，S中存放已确定最短路径的顶点，T中存放待确定最短路径的顶点。初始时，S中仅有一个源点，T中包含除源点外奉命顶点，此时各顶点的当前最短路径长度为源点到该顶点的弧上的权值。接着选取T中当前最短路径长度最小的一个顶点v加入S，然后修改T中剩余顶点的

14、当前最短路径长度，修改的原则是：当v的最短路径长度与v到T中的顶点之间的权值之和小于该顶点的当前最短路径长度时，用前者替换后者。重复上述过程，直至S中包含所有的顶点。6.5 6.5 最短路径和拓扑排序最短路径和拓扑排序迪卡斯特拉（Dijkstra）算法伪码描述如下：S=v；置T中各顶点的距离值；whileS中顶点数n在T中选择距离值最小的顶点u；S=S+u；调整T中剩余顶点的距离值；6.5 6.5 最短路径和拓扑排序最短路径和拓扑排序6.5.2 6.5.2 拓扑排序拓扑排序拓扑排序拓扑排序:对于一个对于一个AOVAOV网，通常需要把它的所有网，通常需要把它的所有顶点排成一个满足下述关系的线性序

15、列顶点排成一个满足下述关系的线性序列v v1 1，v v2 2，v vn n，如果如果AOVAOV网中从顶点网中从顶点v vi i到顶点到顶点v vj j有一条路有一条路径，则在该线性序列中顶点径，则在该线性序列中顶点v vi i必在顶点必在顶点v vj j之前。之前。满足这种线性关系的序列称为拓扑序列满足这种线性关系的序列称为拓扑序列 拓扑排序的算法拓扑排序的算法基本步骤是：基本步骤是：（1）从网中选择一个入度为）从网中选择一个入度为0的顶点并输出；的顶点并输出；（2 2）从网中删除此顶点及其所有出边）从网中删除此顶点及其所有出边 6.5 6.5 最短路径和拓扑排序最短路径和拓扑排序拓扑排序算法描述为：topologicalsort(digraph)fori=l到寻找一个最小顶点v；num(v)=i；从digraph中删除顶点v以及与v相关联的所有边；