数据结构教学全套课件Java版杨淑萍教学资料教学演示文稿 图1图基础及图遍历.ppt

《数据结构教学全套课件Java版杨淑萍教学资料教学演示文稿 图1图基础及图遍历.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图主要内容图的基本概念图的存储图的连通性图的生成树图遍历实践项目：图遍历演示程序图的应用公交网络系统最短路径查询物流系统运输系统基本概念图：图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：Graph＝(V,E)其中V={x

2、x某个数据对象}是顶点的有穷非空集合；E={(x,y)

3、x,yV}或E={

4、x,yV&&Path(x,y)}是顶点之间关系的有穷集合，也叫做边(edge)集合。Path(x,y)表示从x到y的一条单向通路,它是有方向的。有向图和无向图000011112222654

5、33无向图：图的每条边都没有方向，即边的2个顶点没有次序关系（1，0），（0，1）是同一条边有向图：图的每条边都是有方向的，即边的2个顶点有次序关系。<0,1>，<1,0>是2条边带权图（也称网）权：图的边上的具有特定含义的数值称为权。带权图：图的每条边都带有一个权，这样的图称为带权图，也称网。BACD95234BAC523子图邻接顶点如果(u,v)是E(G)中的一条边，则称u与v互为邻接顶点。子图设有两个图G＝(V,E)和G‘＝(V’,E‘)。若V’V且E‘E,则称图G’是图G的子图。0123子图01301230

6、23顶点的度和路径、路径长度0123与顶点关联的边数。顶点0的度为20－1的路径和路径长度：0-3-2-1，路径长度为30-1，路径长度为10-3-2-1-0-1，路径长度为5BACD9523入度为2出度为1连通图与连通分量在无向图中，如果任意2个顶点之间都有路径，则称该无向图是连通图。无向图的极大连通子图称为连通分量。强连通图与强连通分量在有向图中，如果任意2个顶点之间都存在可到达的路径，则称该有向图是强连通图。有向图的极大连通子图称为该有向图的强连通分量。生成树一个n个顶点的连通图的生成树是一个极小连通子图，它含有

7、图中所有的顶点，但具有足以构成一棵树的n-1条边。图的存储邻接矩阵邻接表邻接矩阵(AdjacencyMatrix）在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表，还有一个表示各个顶点之间关系的邻接矩阵。设图A=(V,E)是一个有n个顶点的图,图的邻接矩阵是一个二维数组A.edge[n][n]，定义：无向图的邻接矩阵是对称的;有向图的邻接矩阵可能是不对称的。0123012邻接表(AdjacencyList)1.无向图的邻接表同一个顶点发出的边链接在同一个边链表中，每一个链结点代表一条边(边结点),结点中有另一顶点的

8、下标adjvex和指针nextarc。ABCDdatafirstarcABCD0123adjvexnextarc130210adjvexnextarc2.有向图的邻接表和逆邻接表ABCdatafirstarcABC012邻接表(出边表)ABC012逆邻接表(入边表)102011adjvexnextarcadjvexnextarcadjvexnextarcdatafirstarcBACD69528ABCD01231536283219(出边表)(顶点表)Adjvexinfonextarcdata

9、firstarc3.网络(带权图)的邻接表图的遍历从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历(GraphTraversal)。图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。图的遍历的分类:深度优先搜索遍历DFS(DepthFirstSearch)广度优先搜索遍历BFS(BreadthFirstSearch)深度优先搜索遍历-DFSACDEGBFIHACDEGBFIH12345678912345

10、6789前进回退深度优先搜索过程深度优先生成树DFS在访问图中某一起始顶点v后,由v出发,访问它的任一邻接顶点w1;再从w1出发,访问与w1邻接但还没有访问过的顶点w2;然后再从w2出发,进行类似的访问,…如此进行下去,直至到达所有的邻接顶点都被访问过的顶点u为止。接着,退回一步,退到前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点。如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问;如果没有,就再退回一步进行搜索。重复上述过程,直到连通图中所有顶点都被访问过为止。深度优先搜索遍历(DFS)基本思想

11、广度优先搜索遍历(BFS)ACDEGBFIHACDEGBFH123456789123456789广度优先搜索过程广度优先生成树IBFS在访问了起始顶点v之后,由v出发,依次访问v的各个未被访问过的邻接顶点w1,w2,…,wt,然后再顺序访问w1,w2,…,wt的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有