第八章 图 数据结构（用面向对象的方法与C 语言描述）（第2版）课件.ppt

第八章 图 清华大学计算机系 第八章 图 图的基本概念 图的存储表示 图的遍历与连通性 最小生成树 最短路径 活动网络 图的基本概念 图定义 图是由顶点集合(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 的一条单向通路, 它是有方向的。 有向图与无向图 在有向图中，顶点对 x, y 是有序的。在无向图中，顶点对(x, y)是无序的。 完全图 若有 n 个顶点的无向图有 n(n-1)/2 条边, 则此图为完全无向图。有 n 个顶点的有向图有n(n-1) 条边, 则此图为完全有向图。 邻接顶点 如果 (u, v) 是 E(G) 中的一条边，则称 u 与 v 互为邻接顶点。 子图 设有两个图G＝(V, E) 和G＝(V, E)。若V ? V 且E?E, 则称图G是图G的子图。 权 某些图的边具有与它相关的数, 称之为权。这种带权图叫做网络。 顶点的度 一个顶点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的边。 路径长度 非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和。 简单路径 若路径上各顶点 v1, v2, ..., vm 均不 互相重复, 则称这样的路径为简单路径。 回路 若路径上第一个顶点 v1 与最后一个顶点vm 重合, 则称这样的路径为回路或环。 连通图与连通分量 在无向图中, 若从顶点v1到顶点v2有路径, 则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的, 则称此图是连通图。非连通图的极大连通子图叫做连通分量。 强连通图与强连通分量 在有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径, 则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。 生成树 一个连通图的生成树是其极小连通子图，在 n 个顶点的情形下，有 n-1 条边。 图的抽象数据类型 class Graph { //对象: 由一个顶点的非空集合和一个边集合构成 //每条边由一个顶点对来表示。 public: Graph(); //建立一个空的图 void insertVertex (const T vertex); //插入一个顶点vertex, 该顶点暂时没有入边 void insertEdge (int v1, int v2, int weight); //在图中插入一条边(v1, v2, w) void removeVertex (int v); //在图中删除顶点v和所有关联到它的边 void removeEdge (int v1, int v2); //在图中删去边(v1,v2) bool IsEmpty(); //若图中没有顶点, 则返回true, 否则返回false T getWeight (int v1, int v2); //函数返回边 (v1,v2) 的权值 int getFirstNeighbor (int v); //给出顶点 v 第一个邻接顶点的位置 int getNextNeighbor (int v, int w); //给出顶点 v 的某邻接顶点 w 的下一个邻接顶点 }; 图的存储表示 图的模板基类 在模板类定义中的数据类型参数表 class T, class E 中，T是顶点数据的类型，E是边上所附数据的类型。 这个模板基类是按照最复杂的情况（即带权无向图）来定义的，如果需要使用非带权图，可将数据类型参数表 cla