数据结构第7章图.ppt

* * * * * 7.1.3.2 图的抽象数据类型 基本操作P： CreatGraph（G）输入图G的顶点和边，建立图G的存储。 DestroyGraph（G）释放图G占用的存储空间。 GetVex（G，v）在图G中找到顶点v，并返回顶点v的相关信息。 PutVex（G，v，value）在图G中找到顶点v，并将value值赋给顶点v。 InsertVex（G，v）在图G中增添新顶点v。 DeleteVex（G，v）在图G中，删除顶点v以及所有和顶点v相关联的边或弧。 InsertArc（G，v，w）在图G中增添一条从顶点v到顶点w的边或弧。 DeleteArc（G，v，w）在图G中删除一条从顶点v到顶点w的边或弧。 DFSTraverse（G，v）在图G中，从顶点v出发深度优先遍历图G。 BFSTtaverse（G，v）在图G中，从顶点v出发广度优先遍历图G。 LocateVex（G，u）在图G中找到顶点u，返回该顶点在图中位置。 FirstAdjVex（G，v）在图G中，返回v的第一个邻接点。若顶点在G中没有邻接顶点，则返回“空”。 NextAdjVex（G，v，w）在图G中，返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接点，则返回“空”。 7.2图的存储表示 7.2.1图的存储表示 7.2.2图的邻接矩阵 7.2.3图的邻接表 7.2.4图的十字链表 7.2.5图的邻接多重表 7.2.1图的存储表示 几种常用的图的存储结构: ·邻接矩阵 ·邻接表 ·十字链表 ·邻接多重表 图是一种结构复杂的数据结构，表现在不仅各个顶点的度可以千差万别，而且顶点之间的逻辑关系也错综复杂。从图的定义可知，一个图的信息包括两部分，即图中顶点的信息以及描述顶点之间的关系――边或者弧的信息。因此无论采用什么方法建立图的存储结构，都要完整、准确地反映这两方面的信息。 7.2.2图的邻接矩阵 所谓邻接矩阵（Adjacency Matrix）的存储结构，就是用一维数组存储图中顶点的信息，用矩阵表示图中各顶点之间的邻接关系。假设图G＝（V，E）有n个确定的顶点，即V＝{v0,v1,…,vn-1},则表示G中各顶点相邻关系为一个n×n的矩阵，矩阵的元素为： 若G是网图，则邻接矩阵可定义为： 其中，wij表示边(vi,vj)或vi,vj上的权值；∞表示一个计算机允许的、大于所有边上权值的数。 图的邻接矩阵表示法 邻接矩阵表示法特点 ① 无向图的邻接矩阵一定是一个对称矩阵。因此，在具体存放邻接矩阵时只需存放上（或下）三角矩阵的元素即可。 ② 对于无向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的度TD(vi)。 ③ 对于有向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的出度OD(vi)（或入度ID(vi)）。 ④用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连；但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。这是用邻接矩阵存储图的局限性。 邻接矩阵结构描述 下面介绍图的邻接矩阵存储表示。 在用邻接矩阵存储图时，除了用一个二维数组存储用于表示顶点间相邻关系的邻接矩阵外，还需用一个一维数组来存储顶点信息，另外还有图的顶点数和边数。故可将其形式描述如下： #define MaxVertexNum 100 /*最大顶点数设为100*/ typedef char VertexType; /*顶点类型设为字符型*/ typedef int EdgeType; /*边的权值设为整型*/ typedef struct { VertexType vexs[MaxVertexNum]; /*顶点表*/ EdeType edges[MaxVertexNum][MaxVertexNum]; /*邻接矩阵，即边表*/ int n,e; /*顶点数和边数*/ } Mgragh; /*Maragh是以邻接矩阵存储的图类型*/ 图邻接矩阵存储算法 void CreateMGraph(MGraph *G) { int i,j,k,w; char ch; printf(请输入顶点数和边数(输入格式为:顶点数,边数):\n); scanf(%d,%d,(G-n),(G-e));/*输入顶点数和边数*/