资源描述：
《数据结构(第7章)图》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第七章图计算机与信息技术学院第七章图7.1基本概念和术语7.2图的存储结构7.3图的遍历7.4最小生成树7.5拓扑排序、关键路径7.6最短路径2021/7/202信阳师范学院计算机与信息技术学院7.1基本术语图是顶点集和边集组成的二元组G=,E中每条边是V中一对顶点(u,v)间的联系,如果是无序对，那么称该图为无向图，否则为有向图。邻接点：边的两个顶点互为邻接点关联边：若有边e=(v,u),则称顶点v、u关联边eV0V4V3V1V2V0V1V2V32021/7/203信阳师范学院计算机与信息技术学院顶点V的
2、度=与V相关联的边的数目在有向图中：顶点V的出度=以V为起点有向边数顶点V的入度=以V为终点有向边数顶点V的度=V的出度+V的入度设图G的顶点数为n，边数为e图的所有顶点的度数之和=2*e（每条边对图的所有顶点的度数和“贡献”2度）顶点的度、入度和出度V0V1V2V3V0V4V3V1V22021/7/204信阳师范学院计算机与信息技术学院在图G=中，若有顶点序列v1,v2,…,vk,且E(有向图)或(vi,vi+1)E(无向图)，其中i=1,2,…k-1,v=v1,u=vk,则称该序列
3、是从顶点v到顶点u的路径；若v=u，则称该序列为回路。路径、回路V0V4V3V1V2V0V1V2V32021/7/205信阳师范学院计算机与信息技术学院简单路径、简单回路在一条路径中,除起点和终点外,若其余顶点各不相同,则称该路径为简单路径。由简单路径组成的回路称为简单回路。例如在上面的无向图中，V0,V1,V2,V3是简单路径V0,V1,V2,V4,V1不是简单路径；在下面的有向图中，V0,V2,V3,V0是简单回路。V0V4V3V1V2V0V1V2V32021/7/206信阳师范学院计算机与信息技术学院连通图、强
4、连通图在无（有）向图G=中，若对任何两个顶点u、v都存在从u到v的路径，则称G是连通图(强连通图)。(b)非连通图V0V1V2V3(c)强连通图(a)连通图V0V3V2V1V4V5(d)非强连通图V0V4V3V1V2V0V1V2V32021/7/207信阳师范学院计算机与信息技术学院连通分量、强连通图分量无（有）向图的极大连通子图称为其(强)连通分量。非连通图，有两个连通分量V0V1V2V3非强连通图V0V1V2V3有两个强连通分量V0V3V2V1V4V52021/7/208信阳师范学院计算机与信息技术学院
5、生成树一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。(a)连通图G1V0V4V3V1V2(b)连通图G1的一个生成树V0V4V3V1V22021/7/209信阳师范学院计算机与信息技术学院如果在一棵生成树上添加一条边，必定构成一个环。一棵有n个顶点的生成树有且仅有n-1条边。如果一个图有n个顶点和小于n-1条边，则是非连通图。如果一个图有n个顶点和多于n-1条边，则一定有环。有n-1条边的图不一定是生成树。生成树可能不惟一。生成树的有关性质2021/7/2010信阳师范学
6、院计算机与信息技术学院无向图及其生成树V3V2V4V1V6V5V3V2V4V1V6V5V3V2V4V1V6V5无向图G2021/7/2011信阳师范学院计算机与信息技术学院赋权图546132415102152030410102021/7/2012信阳师范学院计算机与信息技术学院有向图的强连通子图132415220546546132415102152030410102021/7/2013信阳师范学院计算机与信息技术学院例1交通图（公路、铁路）顶点：地点边：连接地点的公路交通图中的单行道双行道，分别用有向边、无向边表示图
7、的应用示例例2电路图顶点：元件边：连接元件之间的线路例3通讯线路图顶点：地点边：地点间的连线例4各种流程图如产品的生产流程图顶点：工序边：各道工序之间的顺序关系2021/7/2014信阳师范学院计算机与信息技术学院7.2图的存储结构图的存储结构至少要保存两类信息：1)顶点的数据2)顶点间的关系约定:G=是图,V={v0,v1,v2,…vn-1},设顶点的角标为它的编号如何表示顶点间的关系？2021/7/2015信阳师范学院计算机与信息技术学院7.2.1图的数组表示法在数组表示法中，用邻接矩阵表示顶点间的关系
8、A[i][j]=1顶点vi与vj间有边(弧)0顶点vi与vj间无边(弧)01010010101011010001100011000000001000V0V4V3V1V2V0V1V2V32021/7/2016信阳师范学院计算机与信息技术学院注：用两个数组分别存储顶点表和邻接矩阵#defineINFINITYINT_MAX//最大值∞#define
