国家建设部网站首页,怎么查看网站公司,合肥网站设计品牌,免费做代理的网站#xff08;1#xff09;已知无向图G各边的权值均为1#xff0c;下列算法中一定能够求出G中从某个顶点到其余各个顶点的最短路径的是#xff08;III#xff09;
I 普利姆算法 II 克鲁斯卡尔算法 III 图的广度优先搜索
#xff08;2#xff09;已知无向图中含有16…1已知无向图G各边的权值均为1下列算法中一定能够求出G中从某个顶点到其余各个顶点的最短路径的是III
I 普利姆算法 II 克鲁斯卡尔算法 III 图的广度优先搜索
2已知无向图中含有16条边其中度为4的节点有三个度为3的节点有4个其他顶点度均小于3图G所含的顶点个数至少为11 16条边则整个图的顶点度数之和为32去掉4*3和3*4个度剩余8则度数小于3的顶点至少有4个故G的顶点至少有11个。
3图的遍历是从给定的源点出发对每一个节点仅访问一次的过程×有些节点可能重复访问所以需要设置状态数组记录节点是否被访问过。
4使用邻接表作为图G的储存结构广度优先搜索的时间复杂度是O|V||E|深度优先搜索的时间复杂度是O(|V||E|。
5G是一个非连通无向图有28条边则该图至少有9个顶点。将该图分位两个连通分量一边是孤立节点另一边是完全连通图此时该图的节点数最少。完全连通图的节点数为n时其边的数量为 n(n-1)/2解得n最少为8故图有9个节点。
6对于n个顶点的强连通图其弧条数至少为nn个顶点的连通图需要n-1条边再加一条边首尾相连。
7最小生成树的代价不一定比该图其他任何一棵生成树的代价小。F与定义矛盾。
