数据结构(Java)图

1、基本内容1.图的定义和基本术语图的定义和基本术语 第第7章章 图图2.图的存储结构图的存储结构 3.图的遍历图的遍历 4.图的最小生成树图的最小生成树 5.最短路径最短路径NEXT Neusoft一.图的定义和基本术语 NEXT Neusoft一.图的定义和基本术语 NEXT Neusoft一.图的定义和基本术语 NEXT Neusoft一.图的定义和基本术语 NEXT Neusoft1.图的定义图的定义 集合集合V和集合和集合E分别为：分别为：V（G）=A,D,T,G,S,W,QE（G）=（A,D），（），（T,G），（），（D,T），（），（G,W），（），（D,S），（），（W,S），）

2、，（A,S），（），（A,Q）一.图的定义和基本术语 AGSTQWDNEXT Neusoft一.图的定义和基本术语 NEXT Neusoft2.图的基本术语图的基本术语 2)完全图完全图 完全图完全图是指图的边数达到最大值，即图中每两个点之间都有边。是指图的边数达到最大值，即图中每两个点之间都有边。 完全无向图完全无向图一.图的定义和基本术语 ASTDNEXT Neusoft一.图的定义和基本术语 NEXT Neusoft2.图的基本术语图的基本术语 3)带权图带权图 带权图带权图是指图中的每条边具有一个权值。是指图中的每条边具有一个权值。一.图的定义和基本术语 ASTKFD51938NEXT

3、 Neusoft2.图的基本术语图的基本术语 4)顶点的度顶点的度 对于无向图，对于无向图，顶点的度是指与该顶点连接的边的数目顶点的度是指与该顶点连接的边的数目。顶点。顶点A的度可以表示为的度可以表示为deg（A） 。对于有向图，对于有向图，顶点的度分为出度与入度顶点的度分为出度与入度。在有向图中，顶点的出度是指由该顶点。在有向图中，顶点的出度是指由该顶点出发的边的数目，用出发的边的数目，用outdeg（）表示；顶点的入度是指指向该顶点边的数目，（）表示；顶点的入度是指指向该顶点边的数目，用用indeg（）表示。（）表示。 一.图的定义和基本术语 NEXT Neusoft2.图的基本术语图的基

4、本术语 5)路径、简单路径和回路路径、简单路径和回路 路径路径是从一个顶点到另一个顶点所经过的顶点序列。是从一个顶点到另一个顶点所经过的顶点序列。简单路径简单路径是指一条路径上，除起点与终点外，其余顶点均不相同的路径。是指一条路径上，除起点与终点外，其余顶点均不相同的路径。若路径的起点与终点相同，则该路径称为若路径的起点与终点相同，则该路径称为回路回路。 一.图的定义和基本术语 NEXT Neusoft2.图的基本术语图的基本术语 6)连通图连通图 在图中，从任意一个顶点出发有路径可以到达该图中的其他任意一个顶点，则该在图中，从任意一个顶点出发有路径可以到达该图中的其他任意一个顶点，则该图为图

5、为连通图连通图，否则该图为，否则该图为非连通图非连通图。 一.图的定义和基本术语 NEXT NeusoftNEXT NeusoftNEXT Neusoft1.邻接矩阵表存储邻接矩阵表存储 邻接矩阵存储邻接矩阵存储是用一维数组存储图中顶点的信息，用矩阵表示图中各顶点之间的是用一维数组存储图中顶点的信息，用矩阵表示图中各顶点之间的邻接关系。若图邻接关系。若图G（V，E）有）有n个顶点，则个顶点，则Av0,v1,vn-1表示表示G中各顶点相中各顶点相邻关系为一个邻关系为一个nn的矩阵，矩阵中元素的值为：的矩阵，矩阵中元素的值为：二.图的存储结构 ，其它0E(G)v,v或)v,(v若1, jijiji

6、ANEXT Neusoft1.邻接矩阵表存储邻接矩阵表存储 二.图的存储结构 NEXT Neusoft1.邻接矩阵表存储邻接矩阵表存储 二.图的存储结构 NEXT Neusoft2.邻接表存储邻接表存储 邻接表存储邻接表存储是将顺序存储与链式存储结合的存储方法。是将顺序存储与链式存储结合的存储方法。邻接表表示法类似于树的孩子链表表示法。邻接表表示法类似于树的孩子链表表示法。对于图对于图G中的每一个顶点中的每一个顶点vi，将所有与顶点，将所有与顶点vi有连线的顶点有连线的顶点vj连成一个单链表，连成一个单链表，这个单链表就称为顶点这个单链表就称为顶点vi的邻接表，再将所有顶点的邻接表表头放到数组

7、中，就的邻接表，再将所有顶点的邻接表表头放到数组中，就构成了图的邻接表。构成了图的邻接表。 二.图的存储结构 NEXT Neusoft2.邻接表存储邻接表存储 二.图的存储结构 NEXT Neusoft2.邻接表存储邻接表存储 二.图的存储结构 noNEXT Neusoft1.深度优先遍历深度优先遍历 （DFS）图的深度优先遍历图的深度优先遍历是以图的某一顶点是以图的某一顶点V0作为出发点，首先访问该点，然后依次从作为出发点，首先访问该点，然后依次从V0的各个未被访问的邻接点出发，进行深度优先遍历，直至图中所有和的各个未被访问的邻接点出发，进行深度优先遍历，直至图中所有和V0相通相通的顶点都被

8、访问到。若此时图中还有顶点未被访问，则以该顶点为起点重复上述的顶点都被访问到。若此时图中还有顶点未被访问，则以该顶点为起点重复上述访问过程，直至图中所有顶点都被访问到为止。访问过程，直至图中所有顶点都被访问到为止。 三.图的遍历 NEXT Neusoft三.图的遍历 NEXT Neusoft三.图的遍历 NEXT Neusoft三.图的遍历 遍历结果为：遍历结果为：A，B，E，D，F，CA，E，D，F，C，BNEXT Neusoft1.深度优先遍历深度优先遍历 voiddsf(intindex)/未找到指定结点，退出未找到指定结点，退出if(vertexsindex=null)return;/

9、创建栈，用于记录已访问结点创建栈，用于记录已访问结点Stacks=newStack(vertexs.length);vertexsindex.visit();s.push(index);三.图的遍历 NEXT Neusoft1.深度优先遍历深度优先遍历 /如果栈不为空，继续如果栈不为空，继续while(!s.isEmpty()index=fNeighbor(s.peek();if(index!=-1)/访问结点访问结点vertexsindex.visit();s.push(index);elses.pop();/清空所有访问标志清空所有访问标志clean();三.图的遍历 NEXT Neuso

10、ft2.广度优先遍历广度优先遍历 广度优先遍历广度优先遍历从图的某一顶点从图的某一顶点V0出发，依次访问出发，依次访问V0未被访问过的邻接点，然后未被访问过的邻接点，然后分别从这些邻接点出发，广度优先遍历图，直至所有邻接点都被访问到。若此时分别从这些邻接点出发，广度优先遍历图，直至所有邻接点都被访问到。若此时图中尚有顶点未被访问，则以该顶点作为起点，重复上述过程，直至图中所有顶图中尚有顶点未被访问，则以该顶点作为起点，重复上述过程，直至图中所有顶点都被访问为止。点都被访问为止。三.图的遍历 NEXT Neusoft2.广度优先遍历广度优先遍历 遍历结果为遍历结果为A，F，D，S，T，W 三.图

11、的遍历 ASTFDWNEXT Neusoft2.广度优先遍历广度优先遍历 voidbsf(intindex)/找不到指定顶点，退出找不到指定顶点，退出if(vertexsindex=null)return;/创建队列，用于存放访问过的结点创建队列，用于存放访问过的结点QStoreq=newQStore(vertexs.length);/访问指定结点访问指定结点vertexsindex.visit();三.图的遍历 NEXT Neusoft2.广度优先遍历广度优先遍历 /将访问过的接点入队将访问过的接点入队q.push(index);/当队列为空时，遍历结束当队列为空时，遍历结束while(!q

12、.isEmpty()index=q.pop();inti;/找队头结点所有的邻接结点，并标记找队头结点所有的邻接结点，并标记while(i=fNeighbor(index)!=-1)vertexsi.visit();q.push(i); 三.图的遍历 NEXT Neusoft三.图的遍历 NEXT Neusoft三.图的遍历 NEXT Neusoft三.图的遍历 NEXT Neusoft三.图的遍历 NEXT Neusoft1.生成树生成树若从图的某顶点出发，可以依次访问到图中所有顶点，则遍历时经过的边和顶点若从图的某顶点出发，可以依次访问到图中所有顶点，则遍历时经过的边和顶点所构成的子图，称

13、作该所构成的子图，称作该图的生成树图的生成树。 图的生产树并不是唯一的图的生产树并不是唯一的。四.图的最小生成树 NEXT Neusoft四.图的最小生成树 NEXT Neusoft四.图的最小生成树 NEXT Neusoft四.图的最小生成树 NEXT Neusoft四.图的最小生成树 求最小生成树的算法(1) 克鲁斯卡尔算法克鲁斯卡尔算法图的存贮结构采用边集数组,且权值相等的边 在数组中排列次序可以是任意的. 该方法对于边相对比较多的不是很实用,浪费时间.(2) 普里姆算法普里姆算法（prim）图的存贮结构采用邻接矩阵.此方法是按各个顶点连通的步骤进行,需要用一个顶点集合,开始为空集,以后

14、将以连通的顶点陆续加入到集合中,全部顶点加入集合后就得到所需的最小生成树 .NEXT Neusoft四.图的最小生成树 NEXT Neusoft四.图的最小生成树 NEXT Neusoft四.图的最小生成树 v1v4v3v6v5v2v7NEXT Neusoft五.最短路径 NEXT Neusoft五.最短路径 NEXT Neusoft五.最短路径 NEXT Neusoft五.最短路径 v1v2v6v7v3v4v52421310258461v1v2v6v7v3v4v52421310258461权值和为负的回权值和为负的回路路注注:假定没有假定没有权值和为负的回路权值和为负的回路,顶点顶点s到顶点

15、到顶点s的路径长度定义为的路径长度定义为0.第6章 图 6.6.1 单源最短路径单源最短路径（单源最短路径（Single-SourceShortestPath）问题：）问题：给定带权有向图（或无向图）给定带权有向图（或无向图）G（V，E）和）和源点源点v0V，求从，求从v0到到G中其余各顶点的中其余各顶点的最短路径最短路径（路径上的权值和达到最小）。（路径上的权值和达到最小）。2/24NEXT NeusoftDijkstra算法思想：算法思想：1、设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组2、第一组为已求出最短路径的顶点集合3、第二组为其余未确定最短路径的顶点集合（用U表示），4、按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。NEXT Neusoft五.最短路径 NEXT Neusoft五.最短路径 NEXT Neusoft五.最短路径 NEXT NeusoftFloyd算法思想：算法思想：1、从任意节点i到任意节