数据结构－第07章－图_02.pptVIP

计算机控制系统 第一讲 第七章 图 主要内容及基本要求 1、主要内容 图的基本概念（7.1节） 图的存储结构（7.2.1节；7.2.2节） 图的遍历 （7.3节） 2、基本要求 了解图的各种存储结构及构造算法 了解掌握图的两种遍历算法 7.2 图的存储结构 数组表示法（邻接矩阵表示） 矩阵行列号表示顶点序号 矩阵的值表示定点间邻接性 1表示邻接，0表示非邻接，或者用权值表示 7.2 图的存储结构-邻接矩阵 数组表示法：存储顶点信息+边或弧的信息 //-----图的数组(邻接矩阵)存储表示 #define INFINITY INT_MAX //最大值∞ #define MAX_VERTEX_NUM 20 //最大顶点个数 typedef enum { DG,DN,UDG,UDN} GraphKind //{有向图、有向网、无向图、无向网} typedef struct ArcCell{ VRType adj; // VRType是顶点关系类型。对无权图，用1或0表示相邻否；对带权图，则为权值类型。 InfoType *info; //该弧相关信息的指针 } AdjMatrix[MAX_VERTEX_NUM] [MAX_VERTEX_NUM] , ArcCell; 7.2 图的存储结构-邻接矩阵 //-----图的数组(邻接矩阵)存储表示 typedef struct { VertexType vexs[[MAX_VERTEX_NUM]]; //顶点向量; AdjMatrix arcs; //邻接矩阵 int vexnum, arcnum; //图的当前顶点数和弧数 GraphKind kind; //图的种类标志 }MGraph 7.2 图的存储结构-邻接矩阵2 邻接矩阵（n个顶点用n阶方阵表示）：便于判断两顶点是否相邻，并计算各自的度。 1或Wij （Vi，Vj）或 Vi，Vj 是E(G)的边或弧 A[i, j]= 0 其它 7.2 图的存储结构-邻接矩阵3 1或Wij 若（Vi，Vj）或 Vi，Vj 是E(G)的边或弧 A[i, j]= 0 其它 7.2 顶点度的计算 顶点Vi的度的计算： 无向图：为第i行（j列）元素之和，即： 有向图：入度ID(vj) =第j列元素之和； 出度OD(vi)=第i行元素之和。 7.2 网的邻接矩阵 1或Wij 若（Vi，Vj）或 Vi，Vj 是E(G)的边或弧 A[i, j]= ∞ 其它 7.2 图的构造操作实现框架 Status CreateGraph(MGraph G){ //采用数组(邻接矩阵)表示法，构造图G. scanf(G.kind); //构建图的类别 swith(G.kind{ case DG: return CreateDG(G); //构造有向图G case DN: return CreateDN(G); //构造有向网G case UDG: return CreateUDG(G); //构造无向图G case UDN: return CreateUDN(G); //构造无向网G default: return ERROR; } } //CreateGraph 7.2 无向网构造操作算法 Status CreateUDN(MGraph G){ //采用数组(邻接矩阵)表示法，构造无向网G。 scanf(G.vexnum, G.arcnum, IncInfo); //IncInfo为0则各弧不含其它信息 for(i=0; iG.vexnum; ++i) scanf(G.vexs[i]); //构造顶点向量 for(i=0; iG.vexnum; ++i) //初始化邻接矩阵 for(j=0; jG.vexnum; ++j) G.arcs[i][j]={INFINITY, NULL}; //无穷或0 for(k=0; kG.arcnum; ++k)