资源描述：
《数据结构与算法教程 朱明方 吴及 第5章 图》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第五章图5.1图的基本概念一.图的定义二.顶点的度三.路径与连通四.图的抽象数据类型5.2图的存储结构一.邻接矩阵二.邻接表三.边集数组四.邻接多重表5.3图的遍历一.深度优先遍历二.广度优先遍历第五章图5.4图的生成树一.图的生成树与最小生成树二.最小生成树与贪心算法5.5最短路径问题一.最短路径的概念二.单源点最短路径三.每对顶点间的最短路径与动态规划算法5.6关键路径一.拓扑序列与AOV网二.AOE网与关键路径三.关键路径的识别第五章图图——反映数据元素间多对多的联系，表现为网状结构；实际问题中的网状结构：•通信网•城
2、市之间的公路网•全国铁路网•销售网•售后服务网•环境监测网…………。第五章图城市间交通网：第五章图计算机网络：计算机网计算机网第五章图实际问题中各种网状关系的抽象——图形结构CABDEF5.1图的基本概念一.图的定义图—图形结构；允许集合中元素间有任意前后件关系；即，数据元素间是多对多的联系；每个元素构成一个顶点；图的二元组定义为：G=(V,E)V—顶点集合，E—V上的一个二元关系；例，图：G1=(V(G1),E(G1))V(G1)={A,B,C}E(G1)={〈A,B〉,〈A,C〉,〈B,C〉,〈C,B〉}每个序偶——一条
3、有向边(带箭头的边)G2=(V(G2),E(G2))V(G2)={v1,v2,v3}E(G2)={(v1,v2),(v1,v3),(v2,v3)}每个无序对——一条无向边(无箭头的边)ABCG1V1V2V3G25.1图的基本概念E(G1)、E(G2)——边(有向边或无向边)的集合；根据图的二元组定义，G=(V,E)有：图——由顶点集合V和边集合E组成；图G1中的边为有向边——有向图；图G2中的边为无向边——无向图；若图G'=(V',E')与图G=(V,E)满足：V(G')⊆V(G),E(G')⊆E(G)则：G'为G的子图例，
4、图G：图G'：G'为G的子图ABCG1V1V2V3G2ABDEFCABCE5.1图的基本概念二.顶点的度无向图：边—(Vi,Vj)，端点Vi、Vj—互为邻接点；顶点的度—顶点连接的边数D(Vi)，每两个顶点间都有边—完全图—边数为最大值n(n-1)/2有向图：边—〈Vi,Vj〉—Vi的出边、Vj的入边；起点Vi：Vj的入边邻接点；终点Vj：Vi的出边邻接点；顶点入度—顶点连接的入边数；D-(Vi)顶点出度—顶点连接的出边数；D+(Vi)顶点的度=顶点入度+顶点出度；设顶点i的度为D(Vi)，图中有n个顶点,边数m为：——握手
5、定理推论：图中度为奇数的顶点有偶数个；例：例：ABDEFABCDm=iijj5.1图的基本概念三.路径与连通1.路径与路径长度无向图，若存在边：(vp,vi1)，(vi1,vi2)，…，(vin-1,vin)，(vin,vq)，有向图，若存在边：≺vp,vi1≻,≺vi1,vi2≻,…,≺vin-1,vin≻,≺vin,vq≻顶点序列(vp,vi1，…，vin,vq)—vp到vq的一条路经；路径长度——路径上所有边的数目；2.简单路径与回路简单路径——所有顶点都不相同的一条路径；回路(环)——起始点与终点相同的路径；简单回路
6、——除起始点与终点外，其余顶点均不重复出现的回路；5.1图的基本概念v4v1v1v2v3v0v5v0v3v2v4简单回路例：v0=v5v0=v4v0v1v2v3v4v5v0v1v2v3v4v5简单路径例：5.1图的基本概念ABDCABDCABDC(c)强连通图(d)强连通分量3.连通图与连通分量顶点vi到vj有路径——vi到vj连通；连通图——任意两顶点都连通的无向图；连通分量——极大的连通子图；强连通图——任意两顶点都连通的有向图；强连通分量——极大的强连通子图；ABCDEABCD(a)连通图(b)连通分量5.1图的基本概
7、念4.关节点与重连通图关节点(articulationpoint)——若在连通图G中删去其中的顶点v及其相关联的边后，使图G分割为两个或两个以上的连通分量，则称顶点v为图G的一个关节点。如下图(a)中J、B、D。(a)非重连通图(b)重连通图重连通图(biconnectedgraph)——无关节点的连通图；如上图(b)特点：任意一对顶点之间至少存在两条路径；ABCDEJHFIABCD5.1图的基本概念5.带权图实际问题中抽象的结果，图中每条边上可以标有具体意义的数值；边上的数值——边的权；边上有权的图——带权图(有值图、网)
8、；如：(a)带权无向图(b)带权有向图ABED5103215C481061752abecd5.1图的基本概念四.图的抽象数据类型ADTGraph{数据：顶点集V，表示顶点间关系的边集合E，以GTGraph为存储类型；操作：//在指针G所指的图中添加一个顶点voidInsertVertex(
