24/12/261“图”专题2012年11级新队员暑假ACM培训主讲：廖枝平24/12/2621)了解图的定义和术语；2)掌握图的各种存储结构；3)掌握图的深度优先搜索和广度优先搜索遍历算法；4)理解最小生成树、最短路径、拓扑排序等图的常用算法。““图”专题学习导读图”专题学习导读主要介绍图的基本概念、图的存储结构和有关图的一些常用算法。学习目的：24/12/263集合:数据元素间的关系是同属一个集合。线性结构：结点间的关系是线性关系，除开始结点和终端结点外，每个结点只有一个直接前趋和直接后继。树形结构：结点间的关系实质上是层次关系，同层上的每个结点可以和下一层的零个或多个结点（即孩子）相关，但只能和上一层的一个结点（即双亲）相关（根结点除外）。图（Graph）结构：对结点（图中常称为顶点）的前趋和后继个数不加限制的，即结点之间的关系是任意的。图是一种较线性表和树更为复杂的非线性结构。是对结点的前趋和后继个数不加限制的数据结构，用来描述元素之间“多对多”的关系。24/12/26424/12/26577.1.1.1.1图的定义图的定义图是由一个顶点集图是由一个顶点集VV和一个弧集和一个弧集RR构成的数据结构成的数据结构。构。Graph=(V,R)Graph=(V,R)VV={={xx||xx某个数据对象某个数据对象}}，是顶点的有穷非空集合；，是顶点的有穷非空集合；R——R——边的有限集合边的有限集合RR={(={(xx,,yy)|)|xx,,yyVV}}无向图或无向图或RR={<={y>||xx,,yyVV&&&&PathPath((xx,,yy)})}有向图有向图是顶点之间关系的有穷集合，也叫做边是顶点之间关系的有穷集合，也叫做边((edge)edge)集合。集合。PathPath((xx,,yy))表示从表示从xx到到yy的一条单向通路的一条单向通路,,它是有方向的。它是有方向的。xx弧尾，弧尾，yy弧头。弧头。77.1.1图及其基本运算图及其基本运算24/12/266有向图与无向图有向图与无向图有向图中：边用有向图中：边用<x,y>表示，且表示，且xx与与yy是有序的。是有序的。a.a.有向图中的边称为“弧”有向图中的边称为“弧”b.x——b.x——弧尾或初始点弧尾或初始点y——y——弧头或终端点弧头或终端点无向图：边用无向图：边用((x,y)x,y)表示，且顶表示，且顶xx与与yy是无序的。是无序的。完全图完全图在具有在具有nn个顶点的有向图中，最大弧数为个顶点的有向图中，最大弧数为nn((nn-1)-1)在具有在具有nn个顶点的无向图中，最大边数为个顶点的无向图中，最大边数为nn((nn-1)/2-1)/2顶点的度顶点的度无向图：与该顶点相关的边的数目无向图：与该顶点相关的边的数目有向图：有向图：入度入度ID(ID(vv))：：以该顶点为头的弧的数目以该顶点为头的弧的数目出度出度OD(OD(vv))：：以该顶点为尾头的弧的数目以该顶点为尾头的弧的数目在有向图中在有向图中,,顶点的度等于该顶点的入度与出度之和。顶点的度等于该顶点的入度与出度之和。24/12/267（a)G1（b)G2（c)G3（d)G45234112346752222364521图图7-17-1无向图和有向无向图和有向图图24/12/268在图7-1中，图(a)为无向图，其中G1的顶点集合和边集合分别为：V(G1)={1，2，3，4，5，6，7}，E(G1)={(1，2)，(l，3)，(2，3)，(3，4)，(3，5)，(5，6)，(5，7)}。图(c)为有向图，其中G3的顶点集合和弧集合分别为V(G3)={1，2，3，4，5，6}，E(G3)={<1，2>，<1，3>，<1，4>，<3，1>，<4，5>，<5，6>，<6，4>}24/12/2697.1.2图的基本术语1．顶点的度与顶点v相关的边或弧的数目称作顶点v的度。在有向图中，一个顶点依附的弧头数目，称为该顶点的入度。一个顶点依附的弧尾数目，称为该顶点的出度，某个顶点的入度和出度之和称为该顶点的度。例如图7-1中，无向图G1中顶点3的度为4，顶点5的度为3。例如在图7-1中，有向图G3中顶点1的出度OD(1)=3，入度ID(1)=1，其度TD(1)=4。24/12/261022．路径和回路．路径和回路在无向图G中，若存在一个顶点序列Vp,Vi1，Vi2，…，Vin，Vq,使得（Vp,Vi1）,(Vi1,Vi2),…..，(Vin,Vq)均属于E（G），则称顶点Vp到Vq存在一条路径。若一条路径上除起点和终点可以相同外，其余顶点均不相同，则称此路径为简单路径。起点和终点相同的路径称为回路；简单路径组成的回路称为简单回路。路径长度...
