数据结构chap007培训资料.ppt

嘉兴学院数学与信息工程学院;7.1 抽象数据类型图的定义;?【重点和难点 】;?【学习指南 】; ADT Graph {　 数据对象： V是具有相同特性的数据元素的集合，称为顶点集。　数据关系：　　VR＝{v,w| v,w∈V且P(v,w)，v,w表示从v到w的弧，并称 v 为弧尾（或初始点），w 为弧头（或终端点），谓词P(v,w)定义了弧v,w的意义或信息 }; 由于“弧”是有方向的，因此称由顶点集和弧集构成的图为有向图。;若v, w?VR 必有w, v?VR,则称 (v,w) 为顶点v 和顶点 w 之间存在一条边。;; 假设图中有 n 个顶点，e 条边，则; 假若顶点v 和顶点w 之间存在一条边或弧，则称顶点v 和w 互为邻接点。;顶点v的出度: 以顶点v为弧尾的弧的数目；; 设图G=(V,{VR})中的一个顶点序列 { u=vi,0,vi,1, …, vi,m=w}中，(vi,j-1,vi,j)?VR 1≤j≤m, 则称从顶点u 到顶点w 之间存在一条路径。 路径上边的数目称作路径长度。; 若无向图G中任意两个顶点之间都有路径相通，则称此图为连通图；; 若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图。; 假设一个连通图有 n 个顶点和 e 条边，其中 n-1 条边和 n 个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树。;结构的建立和销毁;CreatGraph(G, V, VR): // 按定义(V, VR) 构造图;对顶点的访问操作;对邻接点的操作;插入或删除顶点;插入和删除弧;遍 历;;Aij={; 每一行中“1”的个数为该顶点的出度； 每一列中1的个数为该顶点的入度。;#define INFINITY = INT_MAX; 　　　 　// 最大值∞ #define MAX_VERTEX_NUM = 20;　　　　 // 最大顶点个数 typedef enum {DG, DN, AG, AN} GraphKind; 　 // 类型标志{有向图,有向网,无向图,无向网};typedef struct ArcCell { // 弧的定义 VRType adj; // VRType是顶点关系类型。 // 对无权图，用1或0表示相邻否； // 对带权图，则为权值类型。 InfoType *info; // 该弧相关信息的指针 } ArcCell, AdjMatrix[MAX_VERTEX_NUM] [MAX_VERTEX_NUM];;typedef struct { // 图的定义 VertexType // 顶点信息 vexs[MAX_VERTEX_NUM]; AdjMatrix arcs; // 邻接矩阵 int vexnum, arcnum; // 顶点数，弧数 GraphKind kind; // 图的种类标志 } MGraph;;0 A 1 4 1 B 0 4 5 2 C 3 5 3 D 2 5 4 E 0 1 5 F 1 2 3;有向图的邻接表;A;例1： 给出下图的邻接表和邻接矩阵：;例2（习题集P47/7.1)： 给出以下有向图的 1）邻接矩阵 2）每个顶点的入/出度； 3）邻接表及逆邻接表 4）强连能分量;typedef struct ArcNode { int adjvex; // 该弧所指向的顶点的位置 struct ArcNode *nextarc; // 指向下一条弧的指针 InfoType *info; // 该弧相关信息的指针 }