数据结构图.

7.1抽象数据类型图的定义7.2图的存储表示7.3图的遍历7.4最小生成树7.5重（双）连通图和关节点7.6两点之间的最短路径问题7.7拓扑排序7.8关键路径图的基本概念图定义图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：Graph＝(V,E)其中V={x|x某个数据对象}是顶点的有穷非空集合；E={(x,y)|x,yV}或E={x,y|x,yV&&Path(x,y)}是顶点之间关系的有穷集合，也叫做边(edge)集合。Path(x,y)表示从x到y的一条单向通路,它是有方向的。有向图与无向图在有向图中，顶点对x,y是有序的。在无向图中，顶点对(x,y)是无序的。完全图若有n个顶点的无向图有n(n-1)/2条边,则此图为完全无向图。有n个顶点的有向图有n(n-1)条边,则此图为完全有向图。00001111222265433邻接顶点如果(u,v)是E(G)中的一条边，则称u与v互为邻接顶点。子图设有两个图G＝(V,E)和G'＝(V',E')。若V'V且E'E,则称图G'是图G的子图。权某些图的边具有与它相关的数,称之为权。这种带权图叫做网络。子图01230130123023顶点的度一个顶点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的边。路径长度非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和。简单路径若路径上各顶点v1,v2,...,vm均不互相重复,则称这样的路径为简单路径。回路若路径上第一个顶点v1与最后一个顶点vm重合,则称这样的路径为回路或环。012301230123连通图与连通分量在无向图中,若从顶点v1到顶点v2有路径,则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的,则称此图是连通图。非连通图的极大连通子图叫做连通分量。强连通图与强连通分量在有向图中,若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。生成树一个连通图的生成树是其极小连通子图，在n个顶点的情形下，有n-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的意义或信息。图的结构定义:由于“弧”是有方向的，因此称由顶点集和弧集构成的图为有向图。ABECD例如:G1=(V1,VR1)其中V1={A,B,C,D,E}VR1={A,B,A,E,B,C,C,D,D,B,D,A,E,C}若v,wVR必有w,vVR,则称(v,w)为顶点v和顶点w之间存在一条边。BCADFE由顶点集和边集构成的图称作无向图。例如:G2=(V2,VR2)V2={A,B,C,D,E,F}VR2={A,B,A,E,B,E,C,D,D,F,B,F,C,F}名词和术语网、子图完全图、稀疏图、稠密图邻接点、度、入度、出度路径、路径长度、简单路径、简单回路连通图、连通分量、强连通图、强连通分量生成树、生成森林ABECFAEABBC设图G=(V,{VR})和图G=(V,{VR}),且VV,VRVR,则称G为G的子图。1597211132弧或边带权的图分别称作有向网或无向网。假设图中有n个顶点，e条边，则含有e=n(n-1)/2条边的无向图称作完全图；含有e=n(n-1)条弧的有向图称作有向完全图；若边或弧的个数enlogn，则称作稀疏图，否则称作稠密图。假若顶点v和顶点w之间存在一条边，则称顶点v和w互为邻接点，ACDFE例如:ID(B)=3ID(A)=2边(v,w)和顶点v和w相关联。和顶点v关联的边的数目定义为边的度。B顶点的出度:以顶点v为弧尾的弧的数目；ABECF对有向图来说，顶点的入度:以顶点v为弧头的弧的数目。顶点的度(TD)=出度(OD)+入度(ID)例如:ID(B)=2OD(B)=1TD(B)=3设图G=(V,{VR})中的一个顶点序列{u=vi,0,vi,1,…,vi,m=w}中，(vi,j-1,vi,j)VR1≤j≤m,则称从顶点u到顶点w之间存在一条路径。路径上边的数目称作路径长度。ABECF如:长度为3的路径{A,B,C,F}简单路径:序列中顶点不重复出现的路径。简单回路:序列中第一个顶点和最后一个顶点相同的路径。若图G中任意两个顶点之间都有路径相通，则称此图为连通图；若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量。BACDFEBACDFE若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图。ABECFABECF对有向图，否则，其各个强连通子图称作它的强连通分量。假设一个连通图有n个顶点和e条边，其中n-1条边和n个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树。对非连通图，则称由各个连通分量的生成树的集合为此非连通图的生成森林。BACDFE结构的建立和销毁插入或删除顶点对邻接点的操作对顶点的访问操作遍历插入和删除弧基本操作CreatGraph(&G,V,VR)://按定义(V,VR)构造图DestroyGraph(&G)://销毁图结构的建立和销毁对顶点的访问操作LocateVex(G,u);//若G中存在顶点u，则返回该顶点在//图中“位置”；否则返回其它信息。GetVex(G,v);//返回v的值。PutVex(&G,v,value);//对v赋值value。对邻接点的操作FirstAdjVex(G,v);//返回v的“第一个邻接点”。若该顶点//在G中没有邻接点，则返回“空”。NextAdjVex(G,v,w);//返回v的（相对于w的）“下一个邻接//点”。若w是v的最后一个邻接点，则//返回“空”。插入或删除顶点InsertVex(&G,v);//在图G中增添新顶点v。DeleteVex(&G,v);//删除G中顶点v及其相关的弧。插入和删除弧InsertArc(&G,v,w);//在G中增添弧v,w，若G是无向的，//则还增添对称弧w,v。DeleteArc(&G,v,w);//在G中删除弧v,w，若G是无向的，//则还删除对称弧w,v。遍历DFSTraverse(G,v,Visit());//从顶点v起深度优先遍历图G，并对每//个顶点调用函数Visit一次且仅一次。BFSTraverse(G,v,Visit());//从顶点v起广度优先遍历图G，并对每//个顶点调用函数Visit一次且仅一次。7.2图的存储表示一、图的数组(邻接矩阵)存储表示二、图的邻接表存储表示三、有向图的十字链表存储表示四、无向图的邻接多重表存储表示Aij={0(i,j)VR1(i,j)VR一、图的数组(邻接矩阵)存储表示BACDFE定义:矩阵的元素为010010100010000101001001110000011100有向图的邻接矩阵为非对称矩阵ABECF0100100100000101100000100typedefstructArcCell{//弧的定义VRTypeadj;//VRType是顶点关系类型。//对无权图，用1或0表示相邻否；//对带权图，则为权值类型。InfoType*info;//该弧相关信息的指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{//图的定义VertexType//顶点信息vexs[MAX_VERTEX_NUM];AdjMatrixarcs;//弧的信息intvexnum,arcnum;//顶点数，弧数GraphKindkind;//图的种类标志}MGraph;0A141B0452C353D254E015F123BACDFE二、图的邻接表存储表示142301201234ABCDE有向图的邻接表ABECF可见，在有向图的邻接表中不易找到指向该顶点的弧。ABECD有向图的逆邻接表ABCDE30342001234在有向图的邻接表中，对每个顶点，链接的是指向该顶点的弧。typedefstructArcNode{intadjvex;//该弧所指向的顶点的位置structArcNode*nextarc;//指向下一条弧的指针InfoType*info;//该弧相关信息的指针}ArcNode;adjvexnextarcinfo弧的结点结构typedefstructVNode{VertexTypedata;//顶点信息ArcNode*firstarc;//指向第一条依附该顶点的弧}VNode,AdjList[MAX_VERTEX_NUM];datafirstarc顶点的结点结构typedefstruct{AdjListvertices;intvexnum,arcnum;intkind;//图的种类标志}ALGraph;图的结构定义三、有向图的十字链表存储表示弧的结点结构弧尾顶点位置弧头顶点位置弧的相关信息指向下一个有相同弧尾的结点指向下一个有相同弧头的结点typedefstructArcBox{//弧的结构表示inttailvex,headvex;InfoType*info;structArcBox*hlink,*tlink;}VexNode;顶点的结点结构顶点信息数据指向该顶点的第一条入弧指向该顶点的第一条出弧typedefstructVexNode{//顶点的结构表示VertexTypedata;ArcBox*firstin,*firstout;}VexNode;typedefstruct{VexNodexlist[MAX_VERTEX_NUM];//顶点结点(表头向量)intvexnum,arcnum;//有向图的当前顶点数和弧数}OLGraph;有向图的结构表示(十字链表)四、无向图的邻接多重表存储表示typedefstructEbox{VisitIfmark;//访问标记intivex,jvex;//该边依附的两个顶点的位置structEBox*ilink,*jlink;InfoType*info;//该边信息指针}EBox;边的结构表示typedefstruct{//邻接多重表VexBoxadjmulist[MAX_VERTEX_NUM];intvexnum,edgenum;}AMLGraph;顶点的结构表示typedefstructVexBox{VertexTypedata;EBox*firstedge;//指向第一条依附该顶点的边}VexBox;无向图的结构表示7.3图的遍历从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。深度优先搜索广度优先搜索遍历应用举例深度优先搜索DFS(DepthFirstSearch)深度优先搜索的示例ACDEGBFIHACDEGBFIH123456789123456789前进回退深度优先搜索过程深度优先生成树DFS在访问图中某一起始顶点v后,由v出发,访问它的任一邻接顶点w1;再从w1出发,访问与w1邻接但还没有访问过的顶点w2;然后再从w2出发,进行类似的访问,…如此进行下去,直至到达所有的邻接顶点都被访问过的顶点u为止。接着,退回一步,退到前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点。如果有,则访问此顶点,之后再从此顶点出发,进行与