数据结构第七章

-1-第七章图7.1图的概念图的定义：图G=(V,E)V是顶点的有穷非空集合。E是偶对（边）有穷集合。相关术语：顶点、弧、弧头、弧尾、有向图、无向图、无向完全图、有向完全图、稀疏图、稠密图、权、网络、邻接点、度、入度、出度、子图、路径、路径长度、连通图、强连通图、连通分量、强连通分量、生成树。7.2图的存储1.邻接矩阵表示法邻接矩阵：表示顶点之间相互关系的矩阵。设G=(V,E)，具有n个顶点，则：|1(Vi,Vj)或Vi,Vj是边A[i,j]=||0(Vi,Vj)或Vi,Vj不是边若G是网络，则|wij(Vi,Vj)或Vi,Vj是边A[i,j]=||0,∞(Vi,Vj)或Vi,Vj不是边存储结构：typedefstruct{charvexs[n];adjvexarcs[n][n];}graph;无向图（网络）是对称的，可采用压缩存储方法，仅存下三角矩阵（不包括对角线）。创建网络：CREATGRAPH(graph*ga){inti,j,k;floatw;for(i=0;in;i++)ga-vexs[i]=getchar();for(i=0;in;i++)for(j=0;jn;j++)ga-arcs[n][n]=0;for(k=0;kn;k++){scanf(%d%d%f,&i,&j,&w);ga-arcs[i][j]=w;ga-arcs[j][i]=w;}}显然，邻接矩阵的时间复杂度T(n)=O(n2)。显然，邻接矩阵的空间复杂度T(n)=O(n2)。-2-2.邻接表表示法邻接表：对G中每个顶点Vi，把所有邻接于Vi的顶点Vj拉成一个链表，此表称Vi的邻接表。结点结构：边表adjvex|next结点序号指针顶点表vertex|link顶点信息指针边表：无向图的邻接表。出边表：有向图的邻接表。入边表：逆邻接表。顶点表：邻接表的表头向量。结点定义：typedefstructnode{intadjvex;structnode*next;}edgenode;typedefstructnode{vextypevertex;edgenode*link;}vexnode;vexnodega[n];建邻接表：CREATADJLIST(vexnodega[]){inti,j,k;edgenode*s;for(i=0;in;i++)//顶点信息{ga-vextex=getchar();ga[i].link=NULL;}for(k=0;ke;k++)//建立边表{scanf(%d%d,&i,&j);s=malloc(sizeof(edgenode));//头插法s-adjvex=j;s-next=ga[i].link;ga[i].link=s;s=malloc(sizeof(edgenode));//头插法s-adjvex=i;s-next=ga[j].link;ga[j].link=s;}}-3-简单结论：①一个图的邻接矩阵是唯一的，而邻接表不唯一。②每个边表对应矩阵的一行或一列，结点个数为非0元素的个数。③若G是无向图，有2e个边表结点。若G是有向图，有e个边表结点（入边表或出边表）。3.十字链表4.多重链表7.3图的遍历图的遍历：从某个顶点出发，沿着某条路径对图中每个顶点各做一次访问。对于连通图，可一次访问到所有顶点，而非连通图，则需多次遍历。为避免重复访问一个结点，可设一布尔向量visited[n]标记是否访问过。1.深度优先搜索DFS深度优先搜索类似于树的前序遍历。首先，从初态Vi出发，访问Vi，标记已访问。然后，从Vi出发搜索Vi的每一个邻接点Vj，若Vj未访问，则以Vj为新出发点继续搜索。显然，上述定义是递归的，特点是尽可能对纵深方向搜索。遍历所得到的顶点序列称深度优先搜索（DFS）序列。遍历算法：//基于邻接矩阵的DFSintvisited[n];graphg;voidDFS(inti){intj;print(%c,g.vexs[i]);visited[i]=TRUE;for(j=0;jn;j++)if((g.arcs[i][j]==1)&&(!visited[j]))DFS[j];}//基于邻接表上的DFSLvexnodeg1[n];voidDFS(inti){intj;edgenode*p;print(%c,g1.vertex)visited[i]=TRUE;p=g1[i].link;while(p){if(!visited[p-adjvex])DFSL(p-adjvex);p=p-next;}}-4-算法分析：DFS算法----T(n)=O(n2)DFSL算法---T(n)=O(n+e)算法DFS和DFSL所用的辅助空间是标志数组和实现递归所用的栈，因此，S(n)=O(n)。图的邻接矩阵是唯一的，所以DFS序列是唯一的。图的邻接表不是唯一的，所以DFSL序列不唯一。2.广度优先搜索BFS广度优先搜索类似于树的按层遍历。首先，从初态Vi出发，访问Vi，标记已访问。然后，从Vi出发搜索Vi的所有邻接点W1,W2,……Wt，然后，依次访问与W1,W2,……Wt邻接的未访问过的顶点。依此类推……显然，上述方法的特点是尽可能横向搜索因此称广度优先搜索(BFS)。遍历所得到的顶点序列称广度优先搜索（BFS）序列。遍历算法：需引入一个队列保存已访问过的结点(W1,W2,……Wt)。//基于邻接矩阵的BFSvoidBFS(intk){inti,j;SETNULL(Q);print(%c\n,g.vexs[k])visited[k]=TRUE;ENQUEUE(Q,k);while(!EMPTY(Q)){i=DEQUEUE(Q);for(j=0;jn;j++)if((g.arcs[i][j]==1)&&(!visited[j])){print(%c\n,g.vexs[j]);visited[j]=TRUE;ENQUEUE(Q,j);}}}//基于邻接表上的BFSLvoidBFSL(intk){inti;edgenode*p;SETNULL(Q);print(%c\n,g1[k].vertex);visited[k]=TRUE;ENQUEUE(Q,k);while(!EMPTY(Q)){i=DEQUEUE(Q);p=g1[i].link;-5-while(p){if(!visited[p-adjvex]){print(%c\n,g1[p-adjvex].vertex);visited[p-adjvex]=TRUE;ENQUEUE(Q,p-adjvex);}p=p-next;}}}算法分析：BFS算法----T(n)=O(n2)BFSL算法---T(n)=O(n+e)算法BFS和BFSL所用的辅助空间是标志数组和实现算法所需的队列，因此，S(n)=O(n)。图的邻接矩阵是唯一的，所以BFS序列是唯一的。图的邻接表不是唯一的，所以BFSL序列不唯一。3.非连通图的遍历若一个无向图是非连通图，则从图中任意一个顶点出发都不能访问到图中的所有顶点。只能从每个连通分量中选一个顶点作为出发点进行搜索，便可访问到非连通图的所有顶点，因此，需调用前述的DFS、DFSL或BFS、BFSL算法。//调用DFS的非连通图的遍历算法voidTRAVER(){inti;for(i=0;in;i++)visited[i]=FALSE;for(i=0;in;i++){if(!visited[i])DFS(i);print(compend\n);}}以上讨论的遍历算法对有向图也是适用的。7.4生成树和最小生成树树(tree)：在图中，树定义为无回路的连通图。有些图看起来不是树，但若选取一个结点做根，便转化为树。生成树：连通图G的一个子图如果是一棵包含G的所有顶点的树，则称该子图为G的生成树。简单结论：①n个顶点的连通图至少有n-1条边，一定是无回路的的树。②生成树是连通图的极小(边数最少)连通子图。③在生成树中，去掉任何一条边则变为非连通图，添加一条边就必定出现回路。-6-图G=(V,E)是连通图，如何求得生成树？在对G的遍历中，从Vi出发搜索到Vj，并访问。这样，必经过(Vi,Vj)，除起点外，对其它n-1个顶点的的访问必经过n-1条边。由n个顶点和n-1条边所构成的极小连通子图就是一棵生成树。在遍历算法中(DFS、DFSL、BFS、BFSL)只要将打印稍作改动就可得到生成树的算法（将打印语句改成打印边(Vi,Vj)），分别称为DFS生成树BFS生成树。从图的遍历角度而言，生成树还可以定义为：生成树：从图的某个顶点出发，在遍历时所经过的边和所有顶点构成的子图，称作该图的生成树。此定义也适用于有向图。简单结论：①若G是非连通图，则需多次调用遍历算法，得到多个生成树，组成G的生成森林，分别称作DFS生成森林或BFS生成森林。②若G是非连通的有向图，且出发点又不是有向图的根，则遍历时只能得到生成森林。③图的生成树不唯一，从不同顶点出发，可得到不同的生成树。最小生成树：连通网络G=(V,E)边是带权的，我们把生成树各边的权值总和称为生成树的权，并把权值最小的生成树称为G的最小生成树(MinimunSpanningTree)。典型应用：n个城市的通讯网络问题？把n个城市连接起来至少要有n-1条线路。把n个城市连接起来最多要n(n-1)/2条线路。如果用权代表两城市之间的线路长度或造价，那么，显然要选择n-1条线路使得线路总长最短或造价最低。这就势必要构造该图的一棵最小生成树。构造最小生成树的普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法：Prim算法：设G=(V,E)，T=(U,TE)①置T为任意一个顶点U={u0}，置初始候选边集，即关联于u0的边（另一端在V里）②while(T中顶点数n){③从候选边集中选取最短的边(u,v)；④将(u,v)扩充到T中，v也扩充到T中；⑤调整候选的短边集；}改进算法：设T中有k个顶点，则候选边数k(n-k)，不适于全部搜索。只需将n-k个∈V的点关联的边作候选边集即可。结论：连通网络的最小生成树不一定是唯一的，对于权值相等的候选边，可任选一短边扩充到T中，但它们的权值总和是相等的。Prim算法适合于求稠密网的最小生成树。存储结构：typedefstruct//生成树格式{intfromvex,endvex;//起点、终点floatlength;//权值}edge;floatdist[n][n];edgeT[n-1];//生成树n-1条边-7-算法实现：T(n)=O(n2)//Prim算法求最小生成树#includeiostream.h#includestdio.h#definen6//结点数#definee10//边数typedefintvextype;typedefintadjtype;vextypevexs[n];//顶点集adjtypearcs[n][n];//邻接矩阵typedefstruct//生成树格式{intfromvex,endvex;intlength;}edge;edgeT[n-1];//生成树n-1条边voidCREATGRAPH()//建立连通网络{inti,j,k,w;cout请输入六个结点:endl;for(i=0;in;i++)cinvexs[i];cout输入完毕endl;for(i=0;in;i++)for(j=0;jn;j++)arcs[i][j]=10000;//没有权值应为无穷大cout请输入起点,终点,权值endl;for(k=0;ke;k++){cinijw;//无向图arcs[i][j]=w;arcs[j][i]=w;}coutendl;}voidPRIM(){intj,k,m,v,min,max=10000;intd;edgef;for(j=1;jn;j++)//构造初始候选边集{T[j-1].fromvex=0;T[j-1].endvex=j;T