数据结构(Java版)图1(图基础及图遍历)课件.ppt

1、图图主要内容主要内容 图的基本概念图的基本概念 图的存储图的存储 图的连通性图的连通性 图的生成树图的生成树 图遍历图遍历 实践项目：图遍历演示程序实践项目：图遍历演示程序图的应用图的应用 公交网络系统公交网络系统 最短路径查询最短路径查询 物流系统物流系统 运输系统运输系统基本概念基本概念(vertex)：有向图和无向图有向图和无向图00001111222265433 无向图：图的每条边都没有方向，即边的2个顶点没有次序关系（1，0），（0，1）是同一条边 有向图：图的每条边都是有方向的，即边的2个顶点有次序关系。，是2条边带权图（也称网）带权图（也称网）权：图的边上的具有特定含义的数值称为

2、权。带权图：图的每条边都带有一个权，这样的图称为带权图，也称网。BACD95234BAC523子图子图。0123子图子图0130123023顶点的度和路径、路径长度顶点的度和路径、路径长度0123与顶点关联的边数。顶点0的度为201的路径和路径长度：0-3-2-1，路径长度为30-1，路径长度为10-3-2-1-0-1，路径长度为5BACD9523入度为2出度为1连通图与连通图与 连通分量连通分量 在无向图中，如果任意2个顶点之间都有路径，则称该无向图是连通图。无向图的极大连通子图称为连通分量。强连通图与强连通分量强连通图与强连通分量 在有向图中，如果任意2个顶点之间都存在可到达的路径，则称该

3、有向图是强连通图。有向图的极大连通子图称为该有向图的强连通分量。生成树生成树 一个n个顶点的连通图的生成树是一个极小连通子图，它含有图中所有的顶点，但具有足以构成一棵树的n-1条边。图的存储图的存储 邻接矩阵 邻接表 ,),(,.否则否则或者或者如果如果01AEjiEjijiEdge01230101101001011010A.edge012000101010A.edge ABCDdata firstarcABCD0123adjvex nextarc 130210adjvex nextarcABCdata firstarcABC012 ABC012102 011adjvex nextarcadj

4、vex nextarcadjvex nextarcdata firstarcBACD69528ABCD0123 1 53 62 83 21 9Adjvex info nextarcdata firstarc图的遍历图的遍历DFSACDEGBFIHACDEGBFIH123456789123456789前进回退深度优先搜索过程深度优先搜索过程 深度优先生成树深度优先生成树DFS)基本思想基本思想ACDEGBFIHACDEGBFH123456789123456789 广度优先搜索过程广度优先搜索过程 广度优先生成树广度优先生成树IFS)基本思想基本思想实践项目设计步骤实践项目设计步骤1.定义图形结点定义图形结点 GraphNode.java2.定义操作定义操作 GraphADT.java3.定义图形结构定义图形结构 Graph.java4.使用图形结构使用图形结构 GraphUser.java图遍历演示程序图遍历演示程序 UML图图主程序运行界面主程序运行界面实战演练（实战演练（100页）页）对例题5-1进行如下修改1）在Graph类中增加一个方法，输出图的邻接矩阵。2）在Graph类中增加一个方法可以删除某条边。3）用非递归算法实现Graph类中的深度优先搜索遍历方法。4）在GraphDemo类中测试上面的方法。