资源描述：
《graph1_.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第七章图软件学院成少雷7.1基本概念和术语7.2图的存储结构7.3图的遍历7.4最小代价生成树7.5拓扑排序、关键路径7.6最短路径图是顶点集和边集组成的二元组G=顶点数据元素通常称作顶点(vertex)，V就是顶点的有穷非空集合。顶点的序偶，称之为边(edge)，E是边的集合。有向图若代表一条边的顶点序偶是有序的(即边有方向)，则称此图为有向图。弧在有向图里，这种有方向的边称之为弧，用有序对表示，称v为弧尾(Tail)，称w为弧头(Head)7.1基本概念和术语若代表一条边的顶点序偶是无序的(即该边无方向)，则称此图为无向图。V1V3V4V2V1V
2、4V5V2V3有向图G1无向图G2完全图：n个顶点有n(n-1)/2条边的无向图有向完全图：n个顶点有n(n-1)条弧的有向图子图：G=(V,{E})和G1=(V1,{E1})若V1属于V,E1属于E则G1是G的子图V1V1V3V4V2V3V1V3V4V1顶点v的度在无向图中与顶点v相关联的边的数目，记为TD(v)入度(ID(V))：有向图中指向某顶点的弧的数目出度(OD(v))：有向图中从某顶点出发的弧的数目有向图的度TD(v)=ID(V)+OD(v)一个有n个顶点，e条边或弧的图，e和n有如下关系：路径（Path）回路或环（Cycle）简单路径顶点不重复的路径连通两
3、个顶点之间有路径连通图任意两个顶点之间有路径连通分量无向图中的极大连通子图。强连通图有向图中,从v到v’和从v’到v都有路径。强连通分量有向图中极大强连通子图。生成树(SpanningTree):极小连通子图,含有图中全部顶点。但只有足以构成一棵树的n-1条边。一棵有n个顶点的生成树有且仅有n-1条边.如果它有n条边,则一定有环。生成森林7.1基本概念和术语7.2图的存储结构7.3图的遍历7.4最小代价生成树7.5拓扑排序、关键路径7.6最短路径邻接矩阵邻接表十字链表(*)邻接多重表(*)7.2图的存储结构用一个一维数组存储图中顶点的信息，用一个二维数组（称为邻接矩阵）
4、存储图中各顶点之间的邻接关系。假设图G＝(V，E)有n个顶点，则邻接矩阵是一个n×n的方阵，定义为：邻接矩阵arc[i][j]＝1若(vi,vj)∈E（或∈E）0其它#defineINFINITYINT_MAX#defineMAX_VERTEX_NUM20//最大顶点个数typedefenum{DG,DN,AG,AN}GraphKind;//图的类型typedefstructArcCell{VRTypeadj;//顶点关系类型，对无权图用1或0表示是否相邻InfoType*info;//该弧的其他信息}ArcCell,AdjMatrix[Max_Verte
5、x_NUM][Max_Vertex_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//顶点向量AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//当前顶点数和弧数GraphKindkind;//图种类标志}Mgraph;邻接矩阵的存储结构#defineMAX_VERTEX_NUM20//最大顶点个数typedefenum{DG,DN,UDG,UDN}GraphKind;/*图的种类*/typedefcharVertexData;/*假设顶点数据为字符型*//*对于无权图，用1或0表示是否相邻
6、；对带权图，则为权值*/intArcNode[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexDatavexs[MAX_VERTEX_NUM];/*顶点向量*/ArcNodearcs];/*邻接矩阵*/intvexnum,arcnum;/*图的顶点数和弧数*/GraphKindkind;/*图的种类标志*/}MGraph;/*(AdjacencyMatrixGraph)*/邻接矩阵实例V1V3V4V2V1V4V5V2V3有向图G1无向图G2无向图无向图邻接矩阵是对称阵，每条边存储两次;顶点v的度等于二维数组对应行（
7、或列）中值为1的元素个数；判断两顶点v、u是否为邻接点：只需判二维数组对应分量是否为1；顶点不变，在图中增加、删除边：只需对二维数组对应分量赋值1或清0；设图的顶点数为n,用有n个元素的一维数组存储图的顶点,用邻接矩阵表示边,则G占用的存储空间为：n+n2；图的存储空间占用量只与它的顶点数有关，与边数无关；适用于边稠密的图；邻接矩阵存储结构的特点有向图有向图的邻接矩阵不一定是对称的；顶点v的出度(OD(v))：等于二维数组对应行中值为1的元素个数；顶点v的入度(ID(v))：等于二维数组对应列中值为1的元素个数；顶点v的度TD(v)=OD
