数据结构习题课5

数据结构习题第5章吉林大学计算机科学与技术学院谷方明第5章作业5-1，5-7，5-12，5-13，5-14，5-15，5-165-1给出下图所示的邻接矩阵和邻接表EDCBA参考答案EDCBA00110001100000100000100101234512345参考答案：注意头指针数组ABCDΛECDΛCDΛEΛAEΛ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的路]vis[v]=1.pHead[v].WHILE(pNULL)DO(IF(vis[VerAdj(p)]=0)(Path(VerAdj(p),u,flag).IF(flag=TRUE)THENRETURN.)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正在访问中]vis[v]=-1.C2[深度优先遍历]pHead[v].WHILE(pNULL)DO(if(VerAdj(p)=-1)(flag=TRUE.RETURN)if(VerAdj(p)=0)(Cycle(VerAdj(p),flag).IF(flag=TRUE)THENRETURN.)pLink(p).)C3[不存在路]vis[v]=1.flag=FALSE.▌方法二：拓扑排序voidGraph::TopoOrder(){inttop=-1;for(inti=0;in;i++)if(count[i]==0){count[i]=top;top=i;}for(inti=0;in;i++)if(top==-1)//检测图中是否有回路{coutThereisacycleinnetwork!endl;return;}else{intj=top;top=count[top];coutjendl;//输出栈顶jEdge*p=head[j].Adjacent;while(p!=NULL)//把j的所有邻接顶点的入度减1{intk=p-VerAdj;if(--count[k]==0){count[k]=top;top=k;}p=p-link;}}}思考无向图如何判环？5-14对于下图所示的非负有向网络，给出Dijkstra算法产生的由源点2到图中其它顶点的最短路径长度以及路径所经历的顶点，并写出生成过程。2012345650101031515203530参考答案S2123456初始化∞0∞∞∞∞2∞01015∞∞23∞0101540∞234350101530∞2345350101530∞23451350101530∞234516350101530∞2012345650101031515203530参考答案2012345650101031515203530最短路径最短路径长度2→3102→4152→4→5302→4→1352→6∞123456dis350101530∞path4-1224-1s1111105-15试求出下图中所有顶点之间的最短路径参考答案A(-1)A(0)A(1)A(2)A(3)012301230123012301230093093091430914305731050505605960592101100411004110041604324024024052405240Path(-1)Path(0)Path(1)Path(2)Path(3)012301230123012301230-10-10-10-10-1010-1010-13301-1-11-1-1-11-10-11-12-1102-11022-1-1-120-1020-1020-1023-103-133-1-133-1033-1233-1233-1A:B5A-D-BA:C7A-D-CA:D3A-DB:A6B-C-AB:C5B-CB:D9B-C-A-DC:A1C-AC:B6C-A-D-BC:D4C-A-DD:A5D-C-AD:B2D-BD:C4D-C5-16对于图5.39所示的无向网络，利用普里姆和克鲁斯卡尔算法，分别求出其最小支撑树，并写出生成过程234561165106112114191833分析PRIM算法KRUSKALprim算法1216121635121635461216354661112163546611518Kruskal算法3512465512346565123465611512346561116512346561116185-19自由树（即无环连通图）T=(V,E)的直径是树中所有顶点之间最短路径的最大值，试设计一个算法求T的直径，并分析算法的时间复杂度。【分级提示】（1）可用邻接表作为存储结构；（2）引入一个辅助数组保存各顶点的度；（3）执行删除过程；（4）并修正各个顶点的度。分析自由树：没有确定根，即无根树无向还是有向：无向Floyd或DijkstraO(n3)n遍BFSO(n*(n+e))特殊性质O(n+e)：从任意顶点v0开始找到最远点v1，再从v1找到最远点v2，v1到v2就是所求最长路径参考答案算法Diameter(Head,n)/*求无向连通无环图的直径*/D1[找离v0最远的叶子结点v1]FORi←1TOnDOvis[i]←0CREATQ(q).q(1,0).WHILE(NOTQEmpty(q))DO((v,d)q.p←adjacent(Head[v]).WHILE(pNULL)DOIF(vis[VerAdj(p)]=0)THENq(VerAdj(p),d+1).)D2[找离v1最远的叶子结点v2]FORj←1TOnDO(vis[i]←0.f[i]←0.).CREATQ(q).q(v,0).f[i]←v.WHILE(NOTQEmpty(q))DO((u,d)q.p←adjacent(Head[v]).WHILE(pNULL)DOIF(vis[VerAdj(p)]=0)THEN(q(VerAdj(p),d+1).f[VerAdj(p)]←u.))D3[输出v2到v1的最长路径]j←u.WHILE(f[j]j)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！”.行末有回车。样例1样例2输入：43122331输出：No！输入：2112输出：Yes！n-1条边连通无环最简单的做法：n-1条边的连通图连通怎么判断？没有孤立点是否一定连通？