ACM培训资料数据结构与算法

《ACM培训资料数据结构与算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构(DATASTRUCTURE)计算机科学与工程系第七章图图的基本概念图的存储表示图的遍历与连通性最小生成树最短路径活动网络207.1图的基本概念图的定义图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：Graph＝(V,E)其中V={x

2、x某个数据对象}是顶点的有穷非空集合；E={(x,y)

3、x,yV}或E={

4、x,yV&&Path(x,y)}是顶点之间关系的有穷集合，也叫做边(edge)集合。Path(x,y)表示从x到y的一条通路。30有向图与无向图完全图40邻接顶点如果(u,v)是E(G)中的一条边，则称u与v互为邻接顶点。子图设有

5、两个图G＝(V,E)和G’＝(V’,E’),若V’V且E’E,则称图G’是图G的子图。50顶点的度一个顶点v的度是与它相关联的边的条数，记作TD(v)。顶点v的入度是以v为终点(弧头)的有向边的条数,记作ID(v);顶点v的出度是以v为始点(弧尾)的有向边的条数,记作OD(v)。路径在图G＝(V,E)中,若从顶点vi出发,沿一些边经过一些顶点vp1,vp2,…,vpm，到达顶点vj。则称顶点序列(vivp1vp2...vpmvj)为从顶点vi到顶点vj的路径。它经过的边(vi,vp1)、(vp1,vp2)、...、(vpm,vj)应是属于E的边。60路径长度非带权图的路径长度

6、是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和。简单路径若路径上各顶点v1,v2,...,vm均不互相重复,则称这样的路径为简单路径。回路若路径上第一个顶点v1与最后一个顶点vm重合,则称这样的路径为回路或环。简单回路除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫简单回路70例157324G26例245136G1路径：1，2，3，5，6，3路径长度：5简单路径：1，2，3，5回路：1，2，3，5，6，3，1简单回路：3，5，6，3路径：1，2，5，7，6，5，2，3路径长度：7简单路径：1，2，5，7，6回路：1，2，5，7，6，5，2，1简单回路：1，

7、2，3，1807.2图的存储结构1）存储特点在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表；还有一个表示各个顶点之间关系的邻接矩阵。2）邻接矩阵设图A=(V,E)是一个有n个顶点的图，则图的邻接矩阵是一个二维数组A[n][n]，定义：7.2.1邻接矩阵(AdjacencyMatrix)表示法90100网络的邻接矩阵1103）数据类型描述#defineMaxVNum100/*最大顶点数设为100*/typedefXXXVertexType;/*顶点类型*/邻接矩阵类型：typedefintEdgeType;/*边的权值设为整型*/typedefstructArcCell{Ve

8、rtexTypeadj;InfoType*Info;//存弧相关信息}ArcCell,AdjMatrix[MaxVNum][MaxVNum]图类型：typedefstruct{VertexTypevexs[MaxVNum];/*顶点表*/AdjMatrixarcs;/*邻接矩阵，即边表*/intvexnum,arcnum;/*图的顶点数和边数*/}Mgragh;/*Maragh是以邻接矩阵存储的图*/1204）图的创建思路：1307.2.2邻接表(AdjacencyList)1)存储特点对于图G中的每个顶点vi，把所有邻接于vi的顶点vj链成一个单链表，这个单链表称为顶点vi的邻

9、接表；将所有点的邻接表表头放到数组中，就构成了图的邻接表140特点无向图中顶点Vi的度为第i个单链表中的结点数有向图中顶点Vi的出度为第i个单链表中的结点个数顶点Vi的入度为整个单链表中邻接点域值是i的结点个数逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表例G1bdac1234acdbvexdatafirstarc41^1^^3^adjvexnext1501602）数据类型描述＃defineMaxVerNum100/*最大顶点数为100*/邻接表类型：typedefstructArcNode{intadjvex;/*邻接点域*/InfoType*Info;/*表示边上信息

10、的域info*/structArcNode*next;/*指向下一个邻接点的指针域*/}ArcNode;表头结点类型：typedefstructVnode{VertexTypevertex;/*顶点域*/ArcNode*firstedge;/*边表头指针*/}Vnode,AdjList[MaxVertexNum];图的类型：typedefstruct{AdjListvertices;/*邻接表*/intvexnum,arcnum;/*顶点数和边数*/}ALGraph;/*ALGr