ACM培训资料数据结构与算法.pptxVIP

17.1 图的基本概念图的定义 图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构： Graph＝( V, E ) 其中 V = { x | x ? 某个数据对象} 是顶点的有穷非空集合； E = {(x, y) | x, y ? V } 或 E = {x, y | x, y ? V Path (x, y)} 是顶点之间关系的有穷集合，也叫做边(edge)集合。Path (x, y)表示从 x 到 y 的一条通路。第1页/共72页ACM培训资料数据结构与算法全文共72页，当前为第1页。 2 有向图与无向图完全图第2页/共72页ACM培训资料数据结构与算法全文共72页，当前为第2页。 3 邻接顶点 如果 (u, v) 是 E(G) 中的一条边，则称 u 与 v 互为邻接顶点。子图 设有两个图G＝(V, E)和G’＝(V’, E’), 若 V ’? V 且 E’ ?E, 则称 图G’ 是图G 的子图。第3页/共72页ACM培训资料数据结构与算法全文共72页，当前为第3页。 4顶点的度 一个顶点v 的度是与它相关联的边的条数，记作TD(v)。顶点 v 的入度 是以 v 为终点(弧头)的有向边的条数, 记作 ID(v); 顶点 v 的出度是以 v 为始点(弧尾)的有向边的条数, 记作 OD(v)。路径 在图 G＝(V, E) 中, 若从顶点 vi 出发, 沿一些边经过一些顶点 vp1, vp2, …, vpm，到达顶点vj。则称顶点序列 ( vi vp1 vp2 ... vpm vj ) 为从顶点vi 到顶点 vj 的路径。它经过的边(vi, vp1)、(vp1, vp2)、...、(vpm, vj)应是属于E 的边。第4页/共72页ACM培训资料数据结构与算法全文共72页，当前为第4页。 5路径长度 非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和。简单路径 若路径上各顶点 v1,v2,...,vm 均不互相重复, 则称这样的路径为简单路径。回路 若路径上第一个顶点 v1 与最后一个顶点vm 重合, 则称这样的路径为回路或环。简单回路 除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫简单回路 第5页/共72页ACM培训资料数据结构与算法全文共72页，当前为第5页。 6例157324G26例245136G1路径：1，2，3，5，6，3路径长度：5简单路径：1，2，3，5回路：1，2，3，5，6，3，1简单回路：3，5，6，3路径：1，2，5，7，6，5，2，3路径长度：7简单路径：1，2，5，7，6回路：1，2，5，7，6，5，2，1简单回路：1，2，3，1第6页/共72页ACM培训资料数据结构与算法全文共72页，当前为第6页。 77.2 图的存储结构1）存储特点在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表；还有一个表示各个顶点之间关系的邻接矩阵。2）邻接矩阵 设图 A = (V, E)是一个有 n 个顶点的图，则图的邻接矩阵是一个二维数组 A[n][n]，定义：7.2.1 邻接矩阵(Adjacency Matrix)表示法第7页/共72页ACM培训资料数据结构与算法全文共72页，当前为第7页。 8第8页/共72页ACM培训资料数据结构与算法全文共72页，当前为第8页。 9 网络的邻接矩阵第9页/共72页ACM培训资料数据结构与算法全文共72页，当前为第9页。 103）数据类型描述#define MaxVNum 100 /*最大顶点数设为100*/typedef XXX VertexType; /*顶点类型*/邻接矩阵类型： typedef int EdgeType; /*边的权值设为整型*/ typedef struct ArcCell{ VertexType adj; InfoType *Info; // 存弧相关信息 }ArcCell,AdjMatrix[MaxVNum][MaxVNum] 图类型： typedef struct { VertexType vexs[MaxVNum]; /*顶点表*/ AdjMatrix arcs; /*邻接矩阵，即边表*/ int vexnum,arcnum; /*图的顶点数和边数*/ }Mgragh; /*Maragh是以邻接矩阵存储的图*/第10页/共72页ACM培训资料数据结构与算法全文共72页，当