数据结构课件第9章.ppt

第 9 章 图 ;9.1 图的实例及概念 ;图 9.1 几个城市之间的铁路交通图 ; 图9.2表示的是在五支球队之间安排比赛的情况。 图中的点表示球队，而点和点之间的连线则表示了对应的两支球队要进行比赛。 ; 图9.3反映的是王、李、赵等五人之间的认识情况。同样，点代表人，而点和点之间的带箭头的连线则表示位于箭尾的点所对应的人认识箭头所指点对应的人。 图9.3表明，王认识张、吴和李；李认识王和赵，而张、李之间互不认识。 ;图 9.3 人与人之间认识情况示意图 ; 从以上几个例子可以看出，点及点之间的连线可被用来反映客观世界中某些对象之间的特定关系。通常可用点来代表所研究的对象（如城市、球队、人等），而点与点之间的连线则表示这两个对象之间存在着特定的关系（如城市之间有铁路连接、 球队之间要进行比赛、某人认识某人等）。  综上所述，图(graph)是由顶点的有限集合V（顶点数n0）与边的集合E（顶点之间的关系）构成的，可形式化地定义如下： G = (V， E) ;其中，  V = {vi|vi∈data object}； E ={(vi, vj )|vi, vj∈V and P(vi, vj)}。  其中，数据元素vi 称为顶点(vertex)； P(vi, vj)表示在顶点vi 和 vj之间有一条连线，这样一条连线可用顶点的偶对(vi, vj)来表示。 ; 若对任意的(vi, vj)∈E，必有(vj, vi)∈E，并且偶对中顶点的前后顺序不限，则称G为无向图；否则，若(vi, vj)∈E 是顶点的有序偶对，则称G为有向图。通常有向图中代表点与点之间连线的偶对使用尖括号，将其表示为〈vi, vj。，以区别于无向图。 无向图中点的连线(vi, vj)称为边；而有向图中点的连线〈vi, vj〉则称为弧，并称顶点vi为弧头（始点），顶点vj为弧尾（终点）。 ;图 9.4 无向图G1和有向图G2 (a) 无向图G1； (b)有向图G2 ;其中，G1的点集和边集分别为：  V(G1) = {1, 2, 3, 4, 5};  E(G1) = {(1, 2), (1, 3), (2, 3), (2, 4), (2, 5), (3, 5), (4, 5)}。  G2的点集和边集则分别为：  V(G2) = {1, 2, 3, 4, 5};  E(G2) = {〈1, 2〉, 〈1, 3〉, 〈2, 3〉, 〈3, 2〉, 〈2, 4〉, 〈2, 5〉, 〈3, 4〉, 〈5, 4〉, 〈5, 3〉}; ;9.1.2 基本术语 ; 在一个有向图中， 若存在一条弧〈vi, vj〉，则称此弧是顶点vi的一条出弧(outarc)，顶点vj的一条入弧(inarc)；称vi为此弧的起始顶点，简称起点或始点，vj为此弧的终止端点，简称终点；称vi和vj 互为邻接点，并称vj是vi的出弧邻接点，vj是vi的的入弧邻接点。如在图G2中，顶点1有两条出弧〈1，2〉和〈1， 3〉，顶点1的两个出弧邻接点分别为顶点2和3；顶点5有一条入弧〈2，5〉，两条出弧〈5，4〉和〈5，3〉，顶点5的入弧邻接点为顶点2， 两个出弧边邻接点为顶点4和3。 ; 2. 顶点的度、入度、出度 无向图中顶点v的度(degree)定义为以该顶点为一个端点的边的数目，简单地说，就是该顶点的边的数目，记为d(v)。如图G1中顶点1的度为2，顶点2的度为4。  有向图中顶点的度有入度和出度之分。入度是该顶点的入边的数目；出度是该顶点的出边的数目，顶点v的度等于它的入度和出度之和。如图G2中顶点1的入度为0，出度为2，度为2； 顶点5的入度为1，出度为2，度为3。 ; 若一个图中有n个顶点和e条边或弧， 则该图所有顶点的度同边数e满足关系： ; 3. 路径和回路 在一个图G中，从顶点v到顶点v′的一条路径（path）是一个顶点序列(v1, v2, … vm)。其中v1 = v，vm = v′。若此图是无向图， 则(vi-1, vi)∈E(G)(2≤i≤m)；若此图是有向图，则〈vi-1, vi〉∈E(G)(2≤i≤m)。路径长度是指该路径上经过的边或弧的数目若路径上除了前后端点外，所有顶点均不同，则称此路径为简单路径；若路径上前后两端点相同，则称此路径为回路或环（cycle）；前后两端点相同的简单路径被称为简单回路或简单环。 ; 如图9.4中所示的G1中，从顶点1到4存在一条路径（1, 3, 5, 4），其长度为3， 该路径为简单路径；路径（1, 2, 3, 1）为一条简单回路