数据结构习题课课件.ppt
数据结构习题 第 5 章,吉林大学计算机科学与技术学院谷方明,第5章作业,5-1，5-7，5-12，5-13，5-14，5-15，5-16,5-1,给出下图所示的邻接矩阵和邻接表,参考答案,参考答案：注意头指针数组,5-7,用邻接矩阵存储一个包含1000个顶点和1000条边的图，则该图的邻接矩阵中有多少元素？有多少非零元素？该矩阵是否为稀疏矩阵？,参考答案,）矩阵中元素个数：1000000）若图为有向图：非零元素的个数：1000 若图为无向图：非零元素的个数：2000）该矩阵是稀疏矩阵,5-12,设计一个算法，检测采用邻接表方法存储、具有n个顶点的有向图中是否存在从顶点v到顶点u的路径，若存在路径，算法给出信息TRUE，否则，给出信息FALSE.,参考答案,算法Path(v,u.flag)/*判断v到u是否有路.有,flag为TRUE,否则FALSE.vis全局，记录结点访问状态*/P1递归出口 IF(v=u)THEN(flag TRUE.RETURN.)P2依次判断v的邻接顶点是否有到u的路 visv=1.p Headv.WHILE(pNULL)DO(IF(visVerAdj(p)=0)(Path(VerAdj(p),u,flag).IF(flag=TRUE)THEN RETURN.)p Link(p).).P3不存在路 flag=FALSE.,时间复杂度O(n)，空间复杂度O(n)其它方法调用DFS或BFS，检查vis数组，判断是否在一个连通分支。Warshall，判断v、u之间是否连通,5-13,设G（V,E）是有向图，请给出算法，判断G中是否有回路，并要求算法的复杂性为O（n+e）。,方法一：深度优先搜索,思想：深搜时，每个结点有两个状态，标记是否被访问过（0未访问，1已访问过）。判环时，多引入一个状态，标记结点正在访问中（-1正在访问中）。如果一个结点正在访问中，又遍历到该接点，那个存在环路。这种状况是由于出现了反向边，即后代指向祖先的边。如果图中有多个连通分支，需要对每个连通分支都判断。,算法Cycle(v.flag)/*判断以v为起点的连通分支是否有环，若有，flag为TRUE,否则FALSE.vis全局，记录每个点的访问状态*/C1标记v正在访问中 visv=-1.C2深度优先遍历 p Headv.WHILE(pNULL)DO(if(VerAdj(p)=-1)(flag=TRUE.RETURN)if(VerAdj(p)=0)(Cycle(VerAdj(p),flag).IF(flag=TRUE)THEN RETURN.)p Link(p).)C3不存在路 visv=1.flag=FALSE.,方法二：拓扑排序,void Graph:TopoOrder()int top=-1;for(int i=0;in;i+)if(counti=0)counti=top;top=i;,for(int i=0;iVerAdj;if(-countk=0)countk=top;top=k;p=p-link;,思考,无向图如何判环？,5-14,对于下图所示的非负有向网络，给出Dijkstra算法产生的由源点2到图中其它顶点的最短路径长度以及路径所经历的顶点，并写出生成过程。,参考答案,参考答案,最短路径 最短路径长度23 1024 15245 30241 3526,5-15,试求出下图中所有顶点之间的最短路径,参考答案,3,-,1,3,3,-,1,-1,3,3,-1,0,3,3,-1,2,3,3,-1,2,3,3,-1,A:B 5 A-D-BA:C 7 A-D-CA:D 3 A-DB:A 6 B-C-AB:C 5 B-CB:D 9 B-C-A-D,C:A 1 C-AC:B 6 C-A-D-BC:D 4 C-A-DD:A 5 D-C-AD:B 2 D-BD:C 4 D-C,5-16,对于图5.39所示的无向网络，利用普里姆和克鲁斯卡尔算法，分别求出其最小支撑树，并写出生成过程,分析PRIM算法KRUSKAL,prim算法,Kruskal算法,5-19,自由树（即无环连通图）T=(V,E)的直径是树中所有顶点之间最短路径的最大值，试设计一个算法求T的直径，并分析算法的时间复杂度。【分级提示】（1）可用邻接表作为存储结构；（2）引入一个辅助数组保存各顶点的度；（3）执行删除过程；（4）并修正各个顶点的度。,分析,自由树：没有确定根，即无根树无向还是有向：无向Floyd或DijkstraO(n3)n遍BFSO(n*(n+e)特殊性质O(n+e)：从任意顶点v0开始找到最远点v1，再从v1找到最远点v2，v1到v2就是所求最长路径,参考答案,算法Diameter(Head,n)/*求无向连通无环图的直径*/D1 找离v0最远的叶子结点v1 FOR i 1 TO n DO visi 0 CREATQ(q).q(1,0).WHILE(NOT QEmpty(q)DO(v,d)q.p adjacent(Headv).WHILE(pNULL)DO IF(visVerAdj(p)=0)THEN q(VerAdj(p),d+1).),D2 找离v1最远的叶子结点v2 FOR j 1 TO n DO(visi 0.fi 0.).CREATQ(q).q(v,0).fi v.WHILE(NOT QEmpty(q)DO(u,d)q.p adjacent(Headv).WHILE(pNULL)DO IF(visVerAdj(p)=0)THEN(q(VerAdj(p),d+1).fVerAdj(p)u.),D3输出v2到v1的最长路径 j u.WHILE(fjj)DO(PRINT(j).j f(j).PRINT(j).,上机题：无根树,设计算法判断一个无向图G是否为树。若是，输出“Yes！”；否则输出“No！”。输入格式：第1行是空格分隔的两个整数n和m，分别表示无向图的顶点数和边数，n=10000,m=100000。第2到n+1行，每行两个整数a和b，表示顶点a和b之间有一条边，1=a,b=n。键盘输入，不必检查输入错误，输入确保正确。输出格式：屏幕上显示一行，“yes！”或“no！”.行末有回车。,n-1条边连通无环最简单的做法：n-1条边的连通图连通怎么判断？没有孤立点是否一定连通？,
