自由树(即无环连通图)T=(K,E)的直径是树中所有点对间最短路径长度的最大值,即T的直径定义为MAX D
自由树(即无环连通图)T=(K,E)的直径是树中所有点对间最短路径长度的最大值,即T的直径定义为MAX D(u,v),这里D(u,v)表示顶点u到顶点v的最短路径长度(路径长度为路径中所包含的边数)。试写一算法求T的直径,并分析算法的时间复杂度。(时间复杂度越小得分越高。)【中科院计算所1999五、3(20分)】
自由树(即无环连通图)T=(K,E)的直径是树中所有点对间最短路径长度的最大值,即T的直径定义为MAX D(u,v),这里D(u,v)表示顶点u到顶点v的最短路径长度(路径长度为路径中所包含的边数)。试写一算法求T的直径,并分析算法的时间复杂度。(时间复杂度越小得分越高。)【中科院计算所1999五、3(20分)】
第3题
十字链表存储结构;其顶点表结点结构为(data,firstin,firstout),其中data,是顶点的有关信息;firstin是指向以该顶点为弧头的第一条边的指针;firstout是指向以该顶点为弧尾的第一条边的指针。其表结点的结构为(tailvex,headvex,weight,hlink,tlink),其中tailvex、headvex分别为弧尾和弧头在图中的序号;weight是弧上的权值,hlink
第4题
度,现在要从这n个村庄中选择一个村庄建一所医院,问这所医院应建在哪个村庄,才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法,并应用该算法解答如图所示的实例。【中国矿业大学2000十五(15分)】
第6题
数据结构,邻接表结构给以必要的说明;(6分)(2)写出算法描述。(C,类Pascal,类C均可)(14分)【南京理工大学1996四、1(20分)】
第7题
权最大的边”,反复执行这一步骤,直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法,并用程序实现你所给出的算法。注:圈就是回路。【复旦大学1997六(13分)】
第8题
得:V1中的任何两个结点在图G中均不相邻,V2中的任何两个结点在图G中也均不相邻。 (1)请各举一个结点个数为5的二部图和非二部图的例子。 (2)请用C或Pascal编写一个函数BIPARTITE判断一个连通无向图G是否是二部图,并分析程序的时间复杂度。设G用二维数组A来表示,大小为n*n(n为结点个数)。请在程序中加必要的注释。若有必要可直接利用堆栈或队列操作。【浙江大学1998
为了保护您的账号安全,请在“上学吧”公众号进行验证,点击“官网服务”-“账号验证”后输入验证码“”完成验证,验证成功后方可继续查看答案!