-
0 votesanswersviews
Kruskal算法的变化
假设G是具有n个顶点的无向图，在每对顶点之间存在加权边 . 你能用以下结构构建一棵树： v_1-v_2-v_3 -...- v_n，使得树中的每个节点对应于G中的顶点，并且每个节点仅具有除叶之外的一个子节点 . 树边缘的总重量也最小化 . 如果使用类似于Kruskal算法的算法：按升序对原始图中所有边的权重进行排序 . 从最小权重边缘开始，如果添加此边缘不违反上述树结构，则在最终树中添加此边缘，否... -
0 votesanswersviews
Prim和Kruskal的算法复杂性
给定具有权重的无向连通图 . w：E - > {1,2,3,4,5,6,7} - 意味着只有7个重量可能 . 我需要在O（n m）中使用Prim算法和在O（m * a（m，n））中使用Kruskal算法找到生成树 . 我不知道该怎么做，真的需要一些关于权重如何帮助我的指导 . -
-3 votesanswersviews
网格的最小生成树
我对这个想法背后的算法有疑问 . 我们有一个常规网格，例如输入如下所示： 5 5 1 2 3 4 5 100 100 23 100 100 100 100 43 100 100 100 100a 63 100b 100 100 100 83 100 100 这意味着我们有5x5矩阵与每个节点的权重（实际上指向每个单元格的高度） . （a和b点通常不包括演示的坐标）我们应该发现给定2坐标，如4,2... -
0 votesanswersviews
使用邻接列表表示最小生成树
我一直试图解决课堂问题 . 问题是： 给定无向图G，找到G内的最小生成树 . 为了传递这个问题，我的函数必须接收并返回一个邻接列表 . 但是，我不确定如何将输入和输出表示为邻接列表 . from collections import defaultdict class Graph: def __init__(self,vertices): self.V= verti...