资源描述：
《【精品数据结构】图》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、《数据结构》第七章(上)第七章图7.1图的定义和术语7.2图的存储结构7.2.1数组表示法7.2.2邻接表7.3图的遍历7.3.1深度优先搜索7.3.2广度优先搜索7.4图的连通性问题7.4.3最小生成树7.5有向无环图及其应用7.5.1拓扑排序7.6最短路径7.6.1从某个源点到其余各顶点的最短路径7.6.2每一对顶点之间的最短路径图的类型定义参见P1567.1图的定义和术语图的定义：是一种多对多的结构关系，每个元素可以有零个或多个直接前趋；零个或多个直接后继。图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：Graph＝(V,R)其中V={v
2、v某个数据
3、对象}是顶点的有穷非空集合；R={VR}={(v,w)
4、v,wV}基本术语：有向图与无向图在有向图中，顶点对是有序的。在无向图中，顶点对(x,y)是无序的。5367214有向图V={1,2,3,4,5,6,7}VR={<1,3>,<1,2>,<3,7>,<3,6>,<2,5>,<2,6>,<2,4>,<5,7>,<6,7>}有向边又可称为弧,中vi称为狐尾或初始点，vj称为狐头或终端点。无向图5367214V={1,2,3,4,5,6,7}VR={(1,3),(3,4),(4,5),(1,2),(2,6),(2,7),(6,7),(5,6),(1,5)
5、,(1,7)}邻接点及关联若无向图中存在边(v,u)，则称顶点v和u互为邻接点；边(v,u)依附于顶点v和u；或者说边(v,u)和顶点v和u相关联。顶点的度、入度、出度在无向图中： 顶点V的度=与V相关联的边的数目在有向图中：顶点V的出度=以V为狐尾的有向边数顶点V的入度=以V为狐头的有向边数顶点V的度=V的出度+V的入度V0V4V3V1V2V0V1V2V3路径、回路无向图G=（V，{E}）中的顶点序列v1,v2,…,vk,若(vi,vi+1)E(i=1,2,…k-1),v=v1,u=vk,则称该序列是从顶点v到顶点u的路径。 若v=u，则称该序列为回路。在图G1中，V0,V
6、1,V2,V3是V0到V3的路径。V0,V1,V2,V3,V0是回路。V0V4V3V1V2例：有向图G2V0V1V2V3在图G2中，V0,V2,V3是V0到V3的路径。V0,V2,V3,V0是回路。有向图G=（V，{E}）中的顶点序列v1,v2,…,vk,若E(i=1,2,…k-1),v=v1,u=vk,则称该序列是从顶点v到顶点u的路径。 若v=u，则称该序列为回路。例：在一条路径中,若除起点和终点外,所有顶点各不相同,则称该路径为简单路径。由简单路径组成的回路称为简单回路。在图G1中，V0,V1,V2,V3是简单路径。V0,V1,V2,V4,V1不是简单
7、路径。 在图G2中，V0,V2,V3,V0是简单回路。无向图G1有向图G2V0V4V3V1V2V0V1V2V3简单路径和简单回路非连通图连通图强连通图非强连通图V0V1V2V3V0V4V3V1V2V0V1V2V3V0V2V3V1V5V4连通图（强连通图）在无（有）向图G=(V,{E})中，若对任何两个顶点v、u都存在从v到u的路径，则称G是连通图（强连通图）。(a)(b)(c)V0V4V3V1V2V0V4V3V1V2V0V4V3V1V2子图设有两个图G=（V，{E}）、G1=（V1，{E1}），若V1V，E1E，则称G1是G的子图。 例:(b)、(c)是(a)的子图权某些图
8、的边具有与它相关的数,称之为权。这种带权图叫做网络。连通分量（强连通分量）非连通图V0V2V3V1V5V4无向图G的极大连通子图称为G的连通分量。 极大连通子图意思是：该子图是G连通子图，将G的任何不在该子图中的顶点加入，子图不再连通。V0V2V3V1V5V4连通分量有向图G的极大强连通子图称为G的强连通分量。极大强连通子图意思是：该子图是G的强连通子图，将D的任何不在该子图中的顶点加入，子图不再是强连通的。强连通分量V0V1V2V3V0V2V3V1权与网图中边或弧所具有的相关数称为权。表明从一个顶点到另一个顶点的距离或耗费。带权的图称为网。极小连通子图：该子图是G的连通子图，
9、在该子图中删除任何一条边，子图不再连通。 包含无向图G所有顶点的极小连通子图称为G的生成树。对非连通图，则称由各个连通分量的生成树的集合为非连通图的生成森林。连通图G1G1的生成树V0V4V3V1V2V0V4V3V1V2V0V4V3V1V2生成树和生成森林图的几种基本操作参见P158。例：G124137.2.1数组表示法邻接矩阵：表示顶点间相联关系的矩阵。 定义：设G=(V,{E})是有n1个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵：例：15324G2
