C_chap_7.1 图及存储结构new.pptVIP

* ? 第七章 图 7.1 图的定义与术语 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图及其应用 7.6 最短路径 7.1 图的定义与术语 ?1. 定义图：???? Graph= ( V,? R ） ???? 其中:? V={ x| x ∈dataobject? } x 是数据元素，在图中称为顶点。 ??????????? R= { VR }????????????? VR= { x, y | P( x, y )∧( x, y ∈V ) } VR 为顶点间关系的集合， ???????????? x, y 为一条弧；x 为弧尾，y 为弧头；有向图。 ??????????? x, y 为图中的一条边；x, y 称为终端点。无向图。 例： 邻接点：在无向图中 x, y 互为邻接点。 在有向图中，y 邻接自 x，x邻接到y. 顶点的度：无向图中，与v关联的边数， 有向图中，顶点有出度与入度之分。 路径： 无向图? 顶点序列；有向图中，顶点序列中的边必须是有向的。 边的权：表示从一个顶点到另一个顶点的距离或耗费。 子图： 图的一部分。 连通性：u ,v 之间有路径， u, v 之间是连通的；在图 G 中，任意的 vi,vj∈ V，有 vi,vj 连通，图 G 是连通的 连通分量； 图中的极大连通子图。 生成树；图中包含全部顶点的极小连通子图。 结构的建立和销毁 插入或删除顶点 对邻接点的操作 对顶点的访问操作 遍历 插入和删除弧 基本操作 对邻接点的操作 FirstAdjVex(G, v); // 返回 v 的“第一个邻接点” 。若 //该顶点在 G 中没有邻接点，则返回“空”。 NextAdjVex(G, v, w); // 返回 v 的（相对于 w 的） “下一个邻接 点”。若 w 是 v 的最后一个邻接点，则 返回“空”。 遍 历 DFSTraverse(G, v, Visit()); //从顶点v起深度优先遍历图G，并对每 //个顶点调用函数Visit一次且仅一次。 BFSTraverse(G, v, Visit()); //从顶点v起广度优先遍历图G，并对每 //个顶点调用函数Visit一次且仅一次。 7.2 图的存储结构 一、图的数组(邻接矩阵)存储表示 二、图的邻接表存储表示 三、有向图的十字链表存储表示 四、无向图的邻接多重表存储表示 7.2.1 数组表示法 ? 用两个数组分别表示顶点信息及边的信息。??? ????????? 0?? 1?? 0?? 1?? 0???????? 1?? 0?? 1?? 0?? 1? A1=?? 0?? 1?? 0?? 1?? 1??? ? 1?? 0?? 1?? 0?? 0??????? ??? 0?? 1?? 1?? 0?? 0 ?????? 0?? 1?? 1?? 0?????????? 0?? 0?? 0?? 0A2=? 0?? 0?? 0?? 1????? 1?? 0?? 0?? 0 ? Aij={ 0 (i,j)?VR 1 (i,j)?VR B A C D F E 定义:矩阵的元素为 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; #define INFINITY INT_max //最大值 #define MAX_VERTEX_NUM //最大顶点个数 typedef enum {DG,DN,UDG,UDN} GraphKind; //{有向图，有向网，无向图，无向网} ?网的邻接矩阵定义为: A [i