图的ADT和物理实现.ppt

图的应用 为计算机与通信网络的互连建模 把一张地图表示为一组位置以及位置之间的距离，以求得位置之间得最短路径 为网络的流量能力建模 寻找从开始状态到目标状态得路径，如人工智能问题的求解 为计算机算法建模，显示程序状态的变化 为复杂活动各子任务的完成寻找较优顺序，如大型建筑的建造 为家族、商业或军事组织和自然科学分类中的各种关系建模 网型结构小节 客观世界中广泛存在网状结构 图结构也在计算科学领域中被广泛的（创造和）应用 图的定义和基本术语 图Graphs 图可以用 G = (V, E) 来表示,每个图都包括一个顶点集(vertices) V, 和一个边集合(edges) E, 其中E中的每条边都是 V 中某一对顶点之间的连接. 顶点总数记为 |V|, 边的总数记为 |E|. 图Graphs 如果图中的边限定为从一个顶点指向另一个顶点, 则此图称为有向图(directed graph或digraph)。如果图中的边没有方向, 则称之为无向图(undirected graph)。如果图中各顶点均带有标号, 则称之为标号图(labeled graph)。 一条边所连接的两个顶点是相邻的(adjacent), 称为邻接点(neighbors)。连接一对邻接点u、v的边被称为与顶点u、v相关联(incident)的边, 记作(u,v)。每条边都可能附有值或权(weight)。边上标有权的图称为带权图(weighted graph) 顶点的度 在无向图中，与顶点vi(vi?V(G))相关联的边的条数称为vi的度，记为TD(vi) 在有向图中，顶点的度为顶点的入度、出度之和 入度等于以vi为头的弧的数目 出度等于以vi为尾的弧的数目 路径Paths 和回路 Cycles 路径: 如果顶点序列 v1, v2, …, vn 从 vi 到 vi+1 (1 = i n) 的边均存在，则称顶点序列v1, v2, …, vn 构成一条长度为 n-1 的路径(path). 如果路径上的各个顶点都不同，则称这个路径为简单路径(simple path). 一条路径将某个顶点vi 连接到它本身，且其长度大于或等于3，则称此路径为回路(cycle). 如果构成回路的路径是简单路径,除了首尾两个顶点相同以外其他顶点均不同,则称此回路为简单回路(simple cycle). 图 (2) 子图 子图(subgraph)S是指由图G中选出其顶点集的一个子集VS以及与VS中顶点相关联的一些边所构成的图 连通分量Connected Components 如果一个无向图中任意一个顶点到其他任意顶点都至少存在一条路径, 则称此无向图为连通的(connected). 无向图的极大连通子图称为连通分量(connected component). 无环图 和 有向无环图 不带回路的图称为无环图(acyclic graph) 不带回路的有向图称为有向无环图(directed acyclic graph或DAG) 一棵自由树(free tree)就是一个不带有简单回路的无向图, 它是连通的, 且有|V|-1条边 图的ADT Graph ADT class Graph { // Graph abstract class public: virtual int n() =0; // # of vertices virtual int e() =0; // # of edges // Return index of first, next neighbor virtual int first(int) =0; virtual int next(int, int) =0; // Store new edge virtual void setEdge(int, int, int) =0; // Delete edge defined by two vertices virtual void delEdge(int, int) =0; // Weight of edge connecting two vertices virtual int weight(int, int) =0; virtual int getMark(int) =0; virtual void setMark(int, int) =0; }; 图的实现（物理数据结构） 图 的表示法 邻接矩阵(adjacency matrix)表示法 图的邻接矩阵是一个|V|×|V|矩阵。 如果从vi到vj存在一条边, 则对第i行的第j个元素做标记, 否则不做标记 邻接矩阵的空间代价为Θ(|V|2) 邻接表(adjacency list)表示法 邻接表是一个以链表为元