数据结构-图教学幻灯片讲义.ppt

第七章 图;7.1 抽象数据类型图的定义; 图是由一个顶点集 V 和一个弧集 R构成的数据结构。 Graph = (V, R ) 其中，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 之间存在一条边。;名词和术语;A;假设图中有 n 个顶点，e 条边，则; 假若顶点v 和顶点w 之间存在一条边，则称顶点v 和w 互为邻接点，;顶点的出度: 以顶点v 为弧尾的弧的数目;;A;v1; 若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图。; 假设一个连通图有 n 个顶点和 e 条边，其中 n-1 条边和 n 个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树。;A;有向图G4; 网;结构的建立和销毁;CreatGraph(G, V, VR): // 按定义(V, VR) 构造图;对顶点的访问操作;对邻接点的操作;插入或删除顶点;插入和删除弧;遍 历;7.2 图的存储表示;一、图的数组(邻接矩阵)存储表示;网的邻接矩阵可以定义为：;v1;A;图的邻接矩阵表示法的特点： 无向图的邻接矩阵是一个对称矩阵。 无向图中，顶点vi的度是邻接矩阵中第i行（或第i列）的元素之和； 有向图中，顶点vi的入度是邻接矩阵中第i列的元素之和，顶点vi的出度是邻接矩阵中第i行的元素之和。 若邻接矩阵中元素aij的值为1，则vi和vj之间有边或弧相连。 图G的邻接矩阵的空间复杂度为O(n2)，只与顶点数n有关，与边数无关，适合于表示稠密图。;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;;A;A;0;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;;A;尾域;0;弧的结点结构;顶点的结点结构;typedef struct { VexNode xlist[MAX_VERTEX_NUM]; // 顶点结点(表头向量) int vexnum, arcnum; //有向图的当前顶点数和弧数 } OLGraph;;课堂练习： 画出右图所示有向图的十字链表;邻接多重表;A;课堂练习：画出下面的无向图的邻接多重表;0;7.3 图的遍历; 从图中某个顶点V0 出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先有哪些信誉好的足球投注网站遍历图，直至图