Ch_7 图(数据结构)概要1.ppt

线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继。;七桥问题;网络路由问题;一笔画问题;第7章 图(Graph);要求;7.1 图的定义和术语;7.1 图的定义和术语; 如果“弧”是有方向的，称由顶点集和弧集构成的图为有向图(Digraph)。;若v, w?VR 必有w, v?VR, 即VR是对称的，则以无序对（v,w)代替这两个有序对，表示v 和 w 之间的一条边。;名词和术语;假设图中有 n 个顶点，e 条边或弧，不考虑顶点到自身的边或弧。;假设图中有 n 个顶点，e 条边或弧，;1;A;A;顶点的出度OD(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中任意两个顶点之间都有路径相通，则称此图为连通图；;A; 若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图。;一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边;一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧;例;例;连通图;图的抽象数据类型定义;结构的建立和销毁;CreatGraph(G, V, VR)； // 按V和VR的定义构造图;对顶点的访问操作;对邻接点的操作;插入或删除顶点;插入和删除弧;遍历;7.2 图的存储结构;Aij={;有向图的邻接矩阵为非对称矩阵;A;;讨论2 ：有向图的邻接矩阵表示。; 容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等。 n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。;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;;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};//{adj,info};For(k=0;kG.arcnum;++k){//构造邻接矩阵 Scanf(v1,v2,w);//输入一条边依附的顶点及权值 i=LocateVex(G,v1);j=LocateVex(G,v2); //确定v1和v2在G中位置 G.arcs[i][j].adj=w;//弧v1,v2的权值 If(IncInfo) Input(*G.arcs[i][j].info); //若弧含有相关信息,则输入 G.arcs[j][i]=G.arcs[i][j];//置v1,v2的对称弧v2,v1 }Return OK; }//CreateUDN;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;1 4;A;typedef struct ArcNod