数据结构 第七章 图

1图的基本概念图定义图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：Graph＝(V,E)其中V={x|x某个数据对象}是顶点的有穷非空集合；E1={(x,y)|x,yV}或E2={x,y|x,yV&&Path(x,y)}其中，E1是顶点之间关系的有穷集合，也叫做边(edge)集合，此时的图称为无向图。E2表示从x到y的一条弧，且称x为弧尾，y为弧头，这样的图称为有向图。2有向图与无向图在有向图中，顶点对x,y是有序的。在无向图中，顶点对(x,y)是无序的。完全图若有n个顶点的无向图有n(n-1)/2条边,则此图为无向完全图。有n个顶点的有向图有n(n-1)条边,则此图为有向完全图。000011112222654333邻接顶点如果(u,v)是E(G)中的一条边，则称u与v互为邻接顶点。子图设有两个图G＝(V,E)和G‘＝(V’,E‘)。若V’V且E‘E,则称图G’是图G的子图。权某些图的边具有与它相关的数,称之为权。这种带权图叫做网络。0123子图01301230234顶点的度一个顶点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的边。5顶点的出度:以顶点v为弧尾的弧的数目;顶点的入度:以顶点v为弧头的弧的数目。ABECF有向图顶点的度(TD)=出度(OD)+入度(ID)TD(B)=OD(B)+ID(B)=3例如:6路径长度非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和。简单路径若路径上各顶点v1,v2,...,vm均不互相重复,则称这样的路径为简单路径。简单回路若路径上第一个顶点v1与最后一个顶点vm重合,则称这样的路径为回路或环。0123012301237ABECF如:从A到F长度为3的路径{A,B,C,F}8连通图与连通分量在无向图中,若从顶点v1到顶点v2有路径,则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的,则称此图是连通图。非连通图的极大连通子图叫做连通分量。强连通图与强连通分量在有向图中,若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。9无向图,若图中任意两个顶点之间都有路径相通，则称此图为连通图;若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量。BACDFEBACDFE10有向图,若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图。否则，其各个强连通子图称作它的强连通分量。ABECFABECF11生成树:假设一个连通图有n个顶点和e条边，其中n-1条边和n个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树。在极小连通子图中增加一条边，则一定有环。在极小连通子图中去掉一条边，则成为非连通图。BACDFEBACDFE12有n个顶点，n-1条边的图必定是生成树吗？对非连通图，则称由各个连通分量的生成树的集合为此非连通图的生成森林。BACDFEBACDFE13图的存储结构在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表，还有一个表示各个顶点之间关系的邻接矩阵。设图A=(V,E)是一个有n个顶点的图,图的邻接矩阵是一个二维数组A.edge[n][n]，定义：邻接矩阵(AdjacencyMatrix),),(,,]][[.否则或若01AEjiEjijiEdge14无向图的邻接矩阵是对称的;有向图的邻接矩阵可能是不对称的。01230101101001011010A.edge012000101010A.edge15在有向图中,统计第i行1的个数可得顶点i的出度，统计第j列1的个数可得顶点j的入度。在无向图中,统计第i行(列)1的个数可得顶点i的度。16186329542031068053290410A.edge网络的邻接矩阵jiji,ji,jiji,ji,jijiji若或且若或且若,)(,)(),,(]][[0EEEEWA.edge17#defineMaxValueInt_MaxconstintNumEdges=50;//边条数constintNumVertices=10;//顶点个数typedefcharVertexData;//顶点数据类型typedefintEdgeData;//边上权值类型typedefstruct{VertexDatavexList[NumVertices];//顶点表EdgeDataEdge[NumVertices][NumVertices];//邻接矩阵,可视为边之间的关系intn,e;//图中当前的顶点个数与边数}MTGraph;用邻接矩阵表示的结构定义18邻接表(AdjacencyList)邻接表:是图的一种链式存储结构。弧的结点结构adjvex;//该弧所指向的顶点的位置nextarc;//指向下一条弧指针info;//该弧相关信息的指针adjvexnextarcinfo顶点的结点结构datafirstarcdata;//顶点信息firstarc;//指向第一条依附该顶点的弧19无向图的邻接表同一个顶点发出的边链接在同一个边链表中，每一个链结点代表一条边(边结点),结点中有另一顶点的下标dest和指针link。ABCDdataadjABCD0123destlinkdestlink13021020有向图的邻接表和逆邻接表ABCdataadjABC012destlinkdestlink邻接表(出边表)dataadjABC012destlink逆邻接表(入边表)10201121网络(带权图)的邻接表BACD69528dataadjABCD0123destcostlink1536283219(出边表)(顶点表)22带权图的边结点中保存该边上的权值cost。顶点i的边链表的表头指针adj在顶点表的下标为i的顶点记录中，该记录还保存了该顶点的其它信息。在邻接表的边链表中，各个边结点的链入顺序任意，视边结点输入次序而定。设图中有n个顶点，e条边，则用邻接表表示无向图时，需要n个顶点结点，2e个边结点；用邻接表表示有向图时，若不考虑逆邻接表，只需n个顶点结点，e个边结点。25typedefcharVertexData;//顶点数据类型typedefintEdgeData;//边上权值类型typedefstructnode{//边结点intdest;//目标顶点下标EdgeDatacost;//边上的权值Structnode*link;//下一边链接指针}EdgeNode;邻接表表示的图的定义（为算法）26typedefstruct{//顶点结点VertexDatadata;//顶点数据域EdgeNode*firstAdj;//边链表头指针}VertexNode;typedefstruct{//图的邻接表VertexNodeVexList[NumVertices];//邻接表intn,e;//图中当前的顶点个数与边数}AdjGraph;27邻接表的构造算法(无向图)voidCreateGraph(AdjGraphG){cinG.nG.e;//输入顶点个数和边数for(inti=0;iG.n;i++){cinG.VexList[i].data;//输入顶点信息G.VexList[i].firstAdj=NULL;}for(i=0;ie;i++){//逐条边输入cintailheadweight;EdgeNode*p=newEdgeNode;p-dest=head;p-cost=weight;28//链入第tail号链表的前端p-link=G.VexList[tail].firstAdj;G.VexList[tail].firstAdj=p;p=newEdgeNode;p-dest=tail;p-cost=weight;//链入第head号链表的前端p-link=G.VexList[head].firstAdj;G.VexList[head].firstAdj=p;}}29图的遍历从图中某一顶点出发访遍图中所有的顶点，且使每个顶点仅被访问一次，这一过程就叫做图的遍历(TraversingGraph)。图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组visited[]。30辅助数组visited[]的初始状态为0,在图的遍历过程中,一旦某一个顶点i被访问,就立即让visited[i]为1,防止它被多次访问。两种图的遍历方法:深度优先搜索DFS(DepthFirstSearch)广度优先搜索BFS(BreadthFirstSearch)31深度优先搜索DFS(DepthFirstSearch)深度优先搜索过程67ACDEGBFIHACDEGBFIH1234589123456789前进回退深度优先生成树32DFS在访问图中某一起始顶点v后,由v出发,访问它的任一邻接顶点w1;再从w1出发,访问与w1邻接但还没有访问过的顶点w2;然后再从w2出发,进行类似的访问,…如此进行下去,直至到达所有的邻接顶点都被访问过的顶点u为止。接着,退回一步,退到前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点。如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问;如果没有,就再退回一步进行搜索。重复上述过程,直到连通图中所有顶点都被访问过为止。33图的深度优先搜索算法voidGraph_Traverse(AdjGraphG){int*visited=newint[NumVertices];for(inti=0;iG.n;i++)visited[i]=0;//访问数组visited初始化for(inti=0;iG.n;i++)if(!visited[i])DFS(G,i,visited);//从顶点i出发开始搜索delete[]visited;//释放visited}34voidDFS(AdjGraphG,intv,intvisited[]){coutGetValue(G,v)‘’;//访问顶点vvisited[v]=1;//顶点v作访问标记intw=GetFirstNeighbor(G,v);//取v的第一个邻接顶点wwhile(w!=-1){//若邻接顶点w存在if(!visited[w])DFS(G,w,visited);//若顶点w未访问过,递归访问顶点ww=GetNextNeighbor(G,v,w);//取顶点v排在w后的下一个邻接顶点}}35广度优先搜索BFS(BreadthFirstSearch)广度优先搜索过程ACDEGBFIHACDEGBFH123456789123456789广度优先生成树I36BFS在访问了起始顶点v之后,由v出发,依次访问v的各个未被访问过的邻接顶点w1,w2,…,wt,然后再顺序访问w1,w2,…,wt的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，…如此做下去，直到图中所有顶点都被访问到为止。广度优先搜索是一种分层的搜索过程,每向前走一步可能访问一批顶点,不像深度优先搜索那样有往回退的情