《数据结构与算法分析(Java版） 教学课件 ppt 作者 第6章》由会员分享，可在线阅读，更多相关《数据结构与算法分析(Java版） 教学课件 ppt 作者 第6章（18页珍藏版）》请在金锄头文库上搜索。
1、第6章 图,6.1 图的基本概念 6.2 图的存储结构 6.3 图的遍历 6.4 最小生成树 6.5 最短路径和拓扑 排序,6.1 图的基本概念,6.1.1 图的定义 图的定义 :图可用二元组表示：Graph=(V，E)，其中V表示元素（顶点）的非空有限集合；E表示元素之间关系（边）的有限集集合，边是顶点偶对。可以看出图的每个结点有任意多个前驱和后继结点。 有向图和无向图 子图,6.1 图的基本概念,6.1.2 常用术语 完全图 ：在一个有n个顶点的无向图中，若每个顶点到其它（n-1）顶点都有一条边，则图中有n个顶点且有（n*（n-1）/2）条边的图称为无向完全图 邻接点 ：对无向图G=（V，
2、E），若有（V1，V2）E，则称V1和V2互为邻接点 相关边：两个相邻接的点连成的边叫做这两个结点的相关边 度：与每个顶点相连的边的数叫该点的度 入度 ：对有向图中某结点的孤头数（边的终点）称为该结点的入度,6.1 图的基本概念,出度 ：对有向图中某结点的孤尾数（边的终点）称为该结点的出度 路径 ：在一图中若从某个顶点VP出发，沿着一些边经过顶点V1，V2，Vm到达Vg则称顶点序列（VP，V1，V2，Vm，Vg)为从Vp到Vg的路径 回路 ：从一顶点出发又回到该顶点，则所经过的路径称为回路 连通：在无向图中，若从顶点Vi到顶点Vj之间有路径则称这两个顶点是连通的 权：有些图对应每条边有一相应的
3、数值，这个数值称为该边的权 网：带权的图称为网,6.2 图的存储结构,6.2.1 邻接矩阵表示法 邻接矩阵是：设G=（V,E）是具有n个顶点的图，则G的邻接矩阵是一个n*n的方阵，其中矩阵每一行分别对应图的各个顶点；矩阵的每一列分别对应图的各个顶点 邻接矩阵的性质： 1图中各顶点序号确定后，图的邻接矩阵是唯一确定的； 2无向图和无向网的邻接矩阵是一个对称矩阵； 3无向图邻接矩阵中第i行（或第i列）的非0元素的个数即为第i个顶点的度； 4有向图邻接矩阵第i行非0元素个数为第i个顶点的出度，第i列非0元素个数为第i个顶点的入度，第i个顶点的度为第i行与第i列非0元素个数之和； 5无向图的边数等于邻
4、接矩阵中非0元素个数之和的一半，有向图的弧数等于邻接矩阵中非0元素个数之和,6.2 图的存储结构,6.2.2 邻接表表示法 在邻接表表示法中，用一个顺序存储区来存储图中各顶点的数据，并对图中每上顶点vi建立一个单链表（此单链表称之为的vi邻接表），把顶点vi的所有相邻顶点，即其后继顶点的序号链接起来 邻接表与邻接矩阵的关系： 1对应于邻接矩阵的每一行有一个线形链接表； 2链接表的表头对应着邻接矩阵该行的顶点； 3链接表中的每个结点对应着邻接矩阵中该行的一个非零元素； 4对于无向图：一个非零元素表示与该行顶点相邻接的另一个顶点； 5对于有向图：非零元素则表示该行顶点为起点的一条边的终点。,6.2
5、 图的存储结构,邻接表的性质： 1图的邻接表表示不是唯一的，它与表结点的链入次序有关； 2无向图的邻接表中第i个边表的结点个数即为第i个顶点的度； 3有向图的邻接表中第i个出边表的结点个数即为第i个结点的出度，有向图的逆邻接表中第i个入边表的结点个数即为第i个结点的入度； 4无向图的边数等于邻接表中边表结点数的一半，有向图的弧数等于邻接表（逆邻接表）中出边表结点（入边表结点）的数目。,6.2 图的存储结构,6.2.3 关联矩阵 图的另一种矩阵表示法为以顶点和边的关联关系为基础建立矩阵，这个矩阵称之为关联矩阵 定义如下：图G=（V,E）的关联矩阵是一个矩阵，使得,6.3 图的遍历,6.3.1 深
6、度优先搜索遍历 从图中某个顶点出发访问图中所有顶点，且使得每一顶点仅被访问一次，这一过程称之为图的遍历 假定给定图G的初态是所有顶点均未曾访问过，在G中任选一顶点v为初始出发点，则深度优先搜索可定义如下： 从指定的起点v出发(先访问v，并将其标记为已访问过)，访问它的任意相邻接的顶点w1，再访问w1的任一个未访问的相邻接顶点w2，如此下去，直到某顶点已无被访问过的邻接顶点或者它的所有邻接顶点都已经被访问过了，就回溯到它的前驱。如果这个访问和回溯过程返回到遍历开始的顶点，就结束遍历过程。如果图中仍存在一些未访问过的结点，就另选一个未访问过的结点重新开始深度优先搜索遍历。,6.3 图的遍历,深度优
7、先搜索遍历算法表示如下： DFS(v) num(v)=i+; for 所有与v邻接的顶点u if num（u）是0 将edge（uv）连接到edges中； DFS（u）； depthFirstSearch() for 所有向量v num(v)=0; edges=null; i=1; while 有一个向量v使得num(v)是0 DFS（v）； 输出edges;,6.3 图的遍历,6.3.2 广度优先搜索遍历 设图G的初态是所有顶点均未访问过，在G中任选一顶点v为初始出发点，则广度优先搜索遍历的基本思想是：从指定的起点v出发，访问与它相邻的所有顶点w1，w2，；然后再依次访问w1，w2，邻接的尚
8、未被访问的所有顶点，再从这些顶点出发访问与它们相邻接的尚未被访问的顶点，直到所有顶点均被访问过为止。如果图中仍存在一些未访问过的结点，就另选一个未访问过的结点重新开始广度优先搜索遍历。,6.3 图的遍历,深度优先搜索遍历算法（以队列作为基本数据结构）表示如下： breadthFirstSearch() for所有顶点u num(u)=0； edges=null； i=l； while存在一个顶点v使得num(v)=0 num(v)=i+； enqueue(v)；/进入队列 while队列非空 v=dequeue()； for所有和v邻接的顶点u if num(u)是0 num(u)=i+； e
9、nqueue(u)； 将edge(vu)连接到edges中； 输出edges；,6.4 最小生成树,6.4.1 生成树 生成树 ：一个连通图G的子图如果是一棵包含G的所有顶点的树，则该子图称为G的生成树 n个顶点的连通图G的任何生成树一定是包含n个顶点和n-1条边的连通子图（称为G的极小连通子图），反之亦然 生成树具有以下特点: 1如果在生成树中去掉任何一条边，此子图就会变成非连通图； 2任意两个顶点之间有且仅有一条路径，如再增加一条边,就会出现一条回路。 3由遍历连通图G时所经过的边和顶点构成的子图是G的生成树。 普里姆（Prim）算法 克鲁斯卡尔（Kruskal）算法,6.5 最短路径和拓
10、扑排序,6.5.1 最短路径 最短路径问题，即求两个顶点间长度最短的路径 路径长度不是指路径上边数的总和，而是指路径上各边的权值总和 单源路径最短问题是指：对于给定的有向网络G=(V,E)及单个源点v，求从v到G的其余各顶点的最短路径。,6.5 最短路径和拓扑排序,迪卡斯特拉（Dijkstra）算法基本思想是：设置两个顶点集S和T，S中存放已确定最短路径的顶点，T中存放待确定最短路径的顶点。初始时，S中仅有一个源点，T中包含除源点外奉命顶点，此时各顶点的当前最短路径长度为源点到该顶点的弧上的权值。接着选取T中当前最短路径长度最小的一个顶点v加入S，然后修改T中剩余顶点的当前最短路径长度，修改的
11、原则是：当v的最短路径长度与v到T中的顶点之间的权值之和小于该顶点的当前最短路径长度时，用前者替换后者。重复上述过程，直至S中包含所有的顶点。,6.5 最短路径和拓扑排序,迪卡斯特拉（Dijkstra）算法伪码描述如下： S=v； 置T中各顶点的距离值； while S中顶点数n 在T中选择距离值最小的顶点u； S=S+u； 调整T中剩余顶点的距离值； ,6.5 最短路径和拓扑排序,6.5.2 拓扑排序 拓扑排序:对于一个AOV网，通常需要把它的所有顶点排成一个满足下述关系的线性序列v1，v2，vn，如果AOV网中从顶点vi到顶点vj有一条路径，则在该线性序列中顶点vi必在顶点vj之前。满足这种线性关系的序列称为拓扑序列 拓扑排序的算法基本步骤是： （1）从网中选择一个入度为0的顶点并输出； （2）从网中删除此顶点及其所有出边,6.5 最短路径和拓扑排序,拓扑排序算法描述为： topologicalsort(digraph) for i=l到 寻找一个最小顶点v； num(v)=i； 从digraph中删除顶点v以及与v相关联的所有边；,
