《数据结构与算法教程 教学课件 ppt 作者 朱明方 吴及 第5章 图》由会员分享，可在线阅读，更多相关《数据结构与算法教程 教学课件 ppt 作者 朱明方 吴及 第5章 图（145页珍藏版）》请在金锄头文库上搜索。
1、第五章 图,5.1 图的基本概念 一. 图的定义 二. 顶点的度 三. 路径与连通 四. 图的抽象数据类型 5.2 图的存储结构 一. 邻接矩阵 二. 邻接表 三. 边集数组 四. 邻接多重表 5.3 图的遍历 一. 深度优先遍历 二. 广度优先遍历,第五章 图,5.4 图的生成树 一. 图的生成树与最小生成树 二. 最小生成树与贪心算法 5.5 最短路径问题 一. 最短路径的概念 二. 单源点最短路径 三. 每对顶点间的最短路径与动态规划算法 5.6 关键路径 一. 拓扑序列与AOV网 二. AOE网与关键路径 三. 关键路径的识别,第五章 图,图反映数据元素间多对多的联系，表现为网状结构；
2、 实际问题中的网状结构： 通信网 城市之间的公路网 全国铁路网 销售网 售后服务网 环境监测网 。,第五章 图,城市间交通网：,第五章 图,计算机网络：,计算机网,计算机网,第五章 图,实际问题中各种网状关系的抽象图形结构,C,A,B,D,E,F,5.1 图的基本概念,一. 图的定义 图图形结构；允许集合中元素间有任意前后件关系； 即，数据元素间是多对多的联系；每个元素构成一个顶点； 图的二元组定义为： G=( V, E ) V顶点集合， EV上的一个二元关系； 例，图： G1= ( V(G1), E(G1) ) V(G1)= A, B, C E(G1)= A, B, A, C, B, C,
3、C, B 每个序偶一条有向边 (带箭头的边) G2= ( V(G2), E(G2) ) V(G2)= v1, v2, v3 E(G2)= (v1, v2), (v1, v3), (v2, v3) 每个无序对一条无向边(无箭头的边),A B C G1 V1 V2 V3 G2,5.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(
4、G) 则：G 为G的子图 例，图G： 图G ： G 为G的子图,A B C G1 V1 V2 V3 G2,A B D E F,C,A B C E,5.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(V
5、i)，图中有n个顶点, 边数m为： 握手定理 推论：图中度为奇数的顶点有偶数个；,例：,例：,A B C D,m =,i,i,j,j,5.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 图的基本概念,5.1 图的基本概念,A B D C,A B D C,A B D C,(c) 强连通图 (d) 强连通分量,3. 连通图与连通分量 顶点vi到vj有路径vi到 vj连通； 连通图任意两顶点都连通的无向图； 连通分量极大的连通子图； 强连通图任意两顶点都连通的有向图； 强连通分量极大的强连通子图；,A B C,D E,A B C D,(a) 连通图 (b) 连通分量,5.1 图的基本概念,4. 关节点与重连通图 关节点(articulation point)若在连通图G中删去其中的顶点v 及其相关联的边后，使图G分割为两个或两个以上
7、的连通分 量，则称顶点v为图G的一个关节点。如下图(a)中J、B、D。 (a) 非重连通图 (b) 重连通图 重连通图(biconnected graph)无关节点的连通图；如上图(b) 特点： 任意一对顶点之间至少存在两条路径；,A B C,D E,J H F I,A B C,D,5.1 图的基本概念,5. 带权图 实际问题中抽象的结果，图中每条边上可以标有具体意义的 数值； 边上的数值 边的权； 边上有权的图 带权图(有值图、网)； 如： (a) 带权无向图 (b) 带权有向图,A B E D,5 10 3,2 15,C,5.1 图的基本概念,四. 图的抽象数据类型 ADT Graph 数
8、据： 顶点集V，表示顶点间关系的边集合E，以GTGraph为存储 类型； 操作： / 在指针G所指的图中添加一个顶点 void InsertVertex (GTGraph *G, ElemType vertex) / 在图中增加一条权重为 weight 的边 (v1, v2) void InsertEdge (GTGraph *G, int v1, int v2, int weight) voidDeleteVertex (GTGraph *G, int v) / 删除G中顶点v / 删除G中的边(v1, v2) void DeleteEdge (GTGraph *G, int v1, int
9、 v2),5.1 图的基本概念,/ 得到G中的边( v1, v2)上的权值 ElemType Getweight (GTGraph *G, int v1, int v2) / 给出G中顶点v的第1个邻接点 int GetFirstAdja (GTGraph *G, int v, int v1) / 给出G中顶点v相对于v1的下一个邻接点 int GetNextAdja (GTGraph *G, int v, int v1) / 从顶点v出发深度优先遍历G，visit( )为访问顶点的操作 DFSTraverse (GTGraph *G, int v, visit () ) / 从顶点v出发广度
10、优先遍历G，visit( )为对顶点的访问操作 BFSTraverse (GTGraph *G, int v, visit () ) ,5.2 图的存储表示,一. 邻接矩阵表示 1. 方法： 用一维数组存储顶点信息； 用矩阵(二维数组)表示顶点的邻接关系； 设图G中有n 个顶点，其序号为：0，1，n-1, 数组Dn存储顶点信息； 数组GAnn存储边信息 邻接矩阵,5.2 图的存储结构,带权图的邻接矩阵表示: 用二维数组GAnn存储带权图n 个顶点的邻接关系； 表示 任一边的权值，如取大于所有边的权值之和。,5.2 图的存储结构,2. 邻接矩阵表示的建立 图的邻接矩阵表示生成两个数组 顶点数组存
11、放各顶点值；适用各种图 邻接数组表示邻接矩阵；不同类型的图稍有不同 若二维数组GA是图的邻接数组，则其生成过程为： 无权图，元素初始值全为0： 若是无向图，输入边 ( i, j ), 做 GAij= GAji =1； 若是有向图，输入边 , 做 GAij =1； 带权图，初始，对角线元素置为0，其余元素置为MaxValue： 若是无向图，输入 (i, j), 做GAij=GAji=权值； 若是有向图，输入边 , 做GAij=权值；,5.2 图的存储结构,设定邻接矩阵表示的图的结构类型: #define MaxVertexNum 100 typedef struct int Vcnt, Ecnt
12、 ; / 图的顶点数、边数 int digraph ; / 有向图/无向图标志 int weigraph ; / 带权图/不带权图标志 ElemType *adj ; / 邻接矩阵数组 VertexType vexlistMaxVertexNum ; / 顶点数组 int *visited ; / 顶点访问标志 Graph ; 实现基本操作：参考教材,5.2 图的存储结构,建立带权无向图G的邻接矩阵表示： void CreateVex_adj (Graph *G, int n, int digraph, int e, int weigraph) int i, j, k, w ; for (i=
13、0; ivexlisti) ; / 建立顶点数组 initGraph (G, n, digraph, weigraph) ; / 初始化邻接数组 G-Ecnt=e ; / e 图的边数 for (k=1; kadji*n+j= G-adjj*n+i=w ; / i、j边端点、w边权值 注意： 带权图邻接矩阵初始化，对角线元素置为0，其余元素为 (如：MaxValue )。,5.2 图的存储结构,邻接矩阵中容易实现： 查找图中任意一条边或边上的权(带权图)； 查找任意顶点的邻接点； 确定任一顶点的度； 前例： 查找的时间复杂度: O(n)， n 顶点数 当边数n2(稀疏图) 时，存储空间利用率低；,0 1 2,顶点0的出边、 出 度 、 邻接点,顶点0的入度、 入边 、 入边邻接点 ,0 1 2,0 1 2,5.2 图的存储结构,二. 邻接表表示 1. 方法: (1) 每个顶点建立邻接关系单链表顶点邻接表 ； (2) 用向量存各邻接表的头指针、各顶点值； 邻接表结点(边结点)： 表头结点： 无权图，表结点中无权值域；,5.2 图的存储结构,2. 邻接表表示的建立 图的邻接表表示定义两种结点：表头结点、边结点； 表头结点可用静态分配，也可采用动态分配空间； 边结点采用动态分配结点，并形成 n个单链表； 表头结点的建立 各类图相同； 边结点的建立 各种图
