数据结构-第7章图详解.ppt

ADT Graph { 数据对象V：V是具有相同特性的数据元素的集合， 称为顶点集。 数据关系R： R＝{VR} VR＝{v,w| v,w∈V且P(v,w)， v,w表示从v到w的弧， 谓词P(v,w)定义了弧v,w的意义或信息 } 第七章 图 7.1 图的定义和术语 有向图、 无向图、 网、 子图 弧头、 弧尾、 边 完全图、 稀疏图、 稠密图 邻接点、 度、 入度、 出度 路径、 路径长度、 回路 简单路径、 简单回路 连通图、 连通分量、 强连通图、 强连通分量 生成树、 生成森林、 最小生成树 名词和术语 结构的建立和销毁: CreateGraph(G,V,VR); // 按V和VR的定义构造图G。 DestroyGraph(G); // 销毁图G。 对顶点的访问操作: LocateVex(G, u); // 若G中存在顶点u，则返回该顶点 // 在图中位置；否则返回其它信息。 GetVex(G, v); // 返回v的值。 PutVex(G, v, value); // 对v赋值value。 图的基本操作 FirstAdjVex(G, v); // 返回v的第一个邻接点。若该顶点 //在G中没有邻接点，则返回“空”。 NextAdjVex(G, v, w); //返回v的（相对于w的）下一个 // 邻接点。若w是v的最后一个邻 // 接点，则返回“空”。 插入或删除顶点 InsertVex(G, v); // 在图G中增添新顶点v。 DeleteVex(G, v); // 删除G中顶点v及其相关的弧。 对邻接点的操作: 插入和删除弧 InsertArc(G, v, w); // 在G中增添弧v,w，若G是无 // 向的，则还增添对称弧w,v。 DeleteArc(G, v, w); //在G中删除弧v,w，若G是无 // 向的，则还删除对称弧w,v。 遍历 DFSTraverse(G, v, Visit()); // 从顶点v起深度优先遍历图 // G，并对每个顶点调用函数 // Visit一次且仅一次。 BFSTraverse(G, v, Visit()); // 从顶点v起广度优先遍历图 // G，并对每个顶点调用函数 // Visit一次且仅一次。 图的邻接矩阵 7.2 图的存储表示 图的邻接矩阵 1 边或弧 a[I][j]= 0 无 网的邻接矩阵定义 wi,j 边或弧 a[I][j]= 0， 无 一般用二维数组表示 类型描述： #define M_V_NUM 20 typedef struct ArcCell { VertexType adj; InfoType *info } ArcCell, AdjList[M_V_NUM][M_V_NUM]; typedef struct { vertextype vex[m_v_num] AdjList arc; int vexnum, arcnum; // 图的当前顶点数和弧数 int kind; // 图的种类标志 } mgraph; 有关运算见P162 2 邻接表 info nextarc adjvex firstarc data 表结点 头结点 #define MAX_VERTEX_NUM 20 typedef struct ArcNode { int adjvex; struct ArcNode *nextarc; InfoType *info;} ArcNode; //表结点 typedef struct VNode { VertexType data; ArcNode *firstarc; } VNode, AdjList[MAX_VERTEX_NUM]; //头结点 typedef struct {AdjList vertices; int vexnum, arcnum; int kind;} ALGraph; 类似的有逆邻接表 3。十字链表 info tlink hlink headvex tailve