java数据结构第8章图

1、数据结构（数据结构（Java版）版）叶核亚叶核亚数据结构（数据结构（Java版）版） 第1章 绪论 第2章 线性表 第3章 排序 第4章 栈与队列 第5章 数组和广义表 第6章 树和二叉树 第7章 查找第8章 图 第9章 综合应用设计第8章 图 8.1 图的基本知识 8.2 图的存储结构 8.3 图的遍历 8.4 最小代价生成树 8.5 最短路径数据结构（Java版）叶核亚8.1 图的基本知识n8.1.1 图的定义n8.1.2 结点的度n8.1.3 子图n8.1.4 路径、回路及连通性数据结构（Java版）叶核亚8.1.1 图的定义n图（graph）是由结点集合及结点间的关系集合组成的一种数据

2、结构。图中的结点又称为顶点，结点之间的关系称为边（edge）。一个图G记作G=(V, E)n其中，V是结点x的有限集合，E是边的有限集合。即V=x|x某个数据元素集合E=(x,y)|x,yV 或 E=x,y|x,yV n其中，(x,y)表示从结点x到y的一条双向通路，即(x,y)没有方向；x,y表示从结点x到y的一条单向通路，即x,y是有方向的。 数据结构（Java版）叶核亚数据结构（Java版）叶核亚1无向图G1V(G1)=A, B, C, DE(G1)=(C,A), (C,A), (A,D), (A,D), (A,B), (C,B), (B,D)2有向图G2V(G3)=v1, v2, v3

3、E(G3)=v1, v2,v2, v1,v2, v3,v3, v3数据结构（Java版）叶核亚3完全图数据结构（Java版）叶核亚4带权图5相邻结点数据结构（Java版）叶核亚8.1.2 结点的度1度、入度、出度n图中与结点v相关联的边的数目称为结点的度（degree），记作TD(v)。 2度与边的关系niive1)(TD21evvvevvniiniiniiniinii2)(OD)(ID)(TD)(OD)(ID11111数据结构（Java版）叶核亚8.1.3 子图n1子图、真子图n2生成子图n如果G是G的子图，且V=V，称图G是G的生成子图。数据结构（Java版）叶核亚8.1.4 路径、回路及

4、连通性n1路径、路径长度、回路n2有根的图、图的根n3连通图n4强连通图数据结构（Java版）叶核亚8.2 图的存储结构n8.2.1 邻接矩阵n8.2.2 邻接表数据结构（Java版）叶核亚8.2.1 邻接矩阵1邻接矩阵的定义2邻接矩阵与结点的度EvvEvvEvvEvvajijijijiij,),(0,),(1或若或若0101000011000010011110101101101021AA数据结构（Java版）叶核亚3带权图的邻接矩阵jijijijijijijijiijvvEvvEvvvvEvvEvvvvvvwa若或且若或且若0,),(,),(),(0320654009790382730686

5、0525054AA数据结构（Java版）叶核亚4声明以邻接矩阵存储的图类public class Graph1 protected int n; /图的结点个数 protected int mat; /二维数组存储图的邻接矩阵数据结构（Java版）叶核亚8.2.2 邻接表n1无向图的邻接表数据结构（Java版）叶核亚2有向图的邻接表数据结构（Java版）叶核亚3声明以邻接表存储的图类nimport ds_java.OnelinkNode; /单向链表的结点类npublic class Graph2 /以邻接表存储的图类nn private OnelinkNode table; /图的邻接表n数

6、据结构（Java版）叶核亚8.3 图的遍历n8.3.1 深度优先遍历n8.3.2 广度优先遍历数据结构（Java版）叶核亚8.3.1 深度优先遍历n1深度优先遍历算法描述数据结构（Java版）叶核亚2以邻接矩阵存储的图的深度优先遍历算法实现package ds_java;public class Graph1 /以邻接矩阵存储的图类 protected int n; /图的结点个数 protected int mat; /二维数组存储图的邻接矩阵 protected int visited; /访问标记数组 public Graph1(int m1) n=m1.length; mat=new

7、intnn; System.arraycopy(m1,0,mat,0,n); /System类方法，复制数组 visited=new int n; public Graph1() 数据结构（Java版）叶核亚【例8.1】 以邻接矩阵表示的图的深度优先遍历算法测试。import ds_java.Tree1;public class Graph1_ex /图类的测试 public static void main(String args) int mat1=0,1,0,1, /无向图G6的邻接矩阵 1,0,1,1, 0,1,0,1, 1,1,1,0; Graph1 g1=new Graph1(ma

8、t1); g1.depthFirstSearch(); 程序运行结果如下：深度优先遍历Depth first search:数据结构（Java版）叶核亚3以邻接表存储的图的深度优先遍历算法实现import ds_java.OnelinkNode; /单向链表的结点类public class Graph2 extends Graph1 /以邻接表存储的图类 private OnelinkNode table; /图的邻接表 public Graph2(int mat) /以邻接矩阵建立图的邻接表 n=mat.length; /继承Graph1类的成员 table=new OnelinkNoden

9、+1; /建立结点表，多一个元素 OnelinkNode p=null,q; int i,j; for(i=1;i=n;i+) /table0不用， /结点序号i与table中的下标一致 tablei=new OnelinkNode(i); /创建i在结点表中的元素 p=tablei; /建立结点i的出边表 for(j=1;j=n;j+) /查找与i相邻的其他结点j数据结构（Java版）叶核亚8.3.2 广度优先遍历1广度优先遍历算法描述数据结构（Java版）叶核亚2以邻接矩阵存储的图的广度优先遍历算法实现import ds_java.Queue2; /链式队列，元素类型为int public

10、 void breadthFirstSearch() /图的广度优先遍历 /k为起始结点序号 System.out.println(广度优先遍历Breadth first search:); for(int k=1;k); /访问起始结点 visitedi=1; /设置访问标记 q2.enqueue(i); /访问过的结点入队 while(!q2.isEmpty() /队列不空时 i=q2.dequeue(); /出队 if(tablei!=null) /查找有边相连的另一结点 数据结构（Java版）叶核亚8.4 最小代价生成树n8.4.1 树与图n8.4.2 生成树n8.4.3 最小代价生成

11、树数据结构（Java版）叶核亚8.4.1 树与图图8.11 树、森林与图数据结构（Java版）叶核亚【例8.2】 以树结构描述测试假币的称重策略。数据结构（Java版）叶核亚8.4.2 生成树n1生成树的定义n如果图T是无向图G的生成子图且T是树，则图T称为图G的生成树。数据结构（Java版）叶核亚n2生成森林n3带权图的生成树数据结构（Java版）叶核亚8.4.3 最小代价生成树n设G是一个连通的带权图，w(e)为边e上的权，T为G的生成树，那么T中各边权之和为n上式称为生成树T的权，也称为生成树的代价（cost）。权最小的生成树称为最小生成树或最小代价生成树。TeewTw)()(数据结构（Java版）叶核亚1克鲁斯卡尔算法数据结构（Java版）叶核亚2普里姆算法数据结构（Java版）叶核亚8.5 最短路径n1单源最短路径源 点终 点路 径路径长度最短路径v1v2(v1, v2)2(v1, v3, v2)12v 3(v1, v3)4(v1, v2, v3)10v 4(v1, v4)5(v1, v3, v4)10v 5(v1, v2, v5)11(v1, v3, v5)7(v1, v4, v5)12数据结构（Java版）叶核亚2所有结点之间的最短路径表8.2 最短路径表源 点终 点最短路径路径长度v1v