题目内容

求图的最小生成树有两种算法，__________算法适合于求稀疏图的最小生成树。【南京理工大学2001二、6(2分)】【北京交通大学2005二、7(2分)】

查看答案

搜索结果不匹配？点我反馈

更多问题

当一个AOV网用邻接表表示时，可按下列方法进行拓扑排序。(1)查邻接表中入度为的顶点，并进栈；(2)若栈不空，则①输出栈顶元素Vj，并退栈；②查Vj的直接后继Vk，对Vk入度处理，处理方法是，若入度为，则Vk进栈；(3)若栈空时，输出顶点数小于图的顶点数，说明有，否则拓扑排序完成。【南京理工大学1996二、3(6分)】

下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n个顶点V1，V2，…，Vn，用相邻矩阵A表示，边的权全是正数。请在下列画线处填上正确叙述。(1)若(Vi，Vj)是边，则A(i，j)的值等于，若(Vi，Vj)不是边，则A(i，j)的值是一个比任何边的权，矩阵的对角线元素全为0。(2)构造最小生成树过程中，若顶点Vi已包括进生成树，就把相邻矩阵的对角线元素A(i，i)置成，若(Vi，Vj)已包括进生成树，就把矩阵元素A(i，j)置成。(3)算法结束时，相邻矩阵中的元素指出最小生成树的。【山东工业大学1998二、4(6分)】

在有向图的邻接矩阵中，若主对角线以下的元素均为零，则该图的拓扑有序序列是__________的。【电子科技大学2005二、3(1分)】

有向图G=(V，E),其中V(G)={0，1，2，3，4，5}，用三元组表示弧及弧上的权d。E(G)为E(G)={<0，5，100>，<0，2，10>，<1，2，5>，<0，4，30>，<4，5，60>，<3，5，10>，<2，3，50>，<4，3，20>)，则从源点0到顶点3的最短路径长度是，经过的中间顶点是。【南京理工大学1998三、6(4分)】