我有这个硬件:
我得3分有问题。正确输出。也就是说,文件1应该输出[[1],[0,2,3],[1],[1]]
,我得到了[[1,2],[0,3],[0],[1]]
,这有点正常,因为它们都是来自文件1的n=4
的生成树
但主要的问题是:对于文件2,我不知道我的代码有什么问题:我得到:[[10], [], [10], [10], [], [], [], [], [], [], [0, 3, 2], [], []]
代码末尾的文件的数据。
(编辑:从tree=[]
开始是问题所在,其余的没有问题)
下面是我对这个问题的尝试:
import itertools
edge_i=[]
edge_j=[]
x = []
y = []
edgelist = []
n = int(input("Enter value for n:")) #input n for number of vertices
adjlist = [[] for i in range(n)] #create n sublists inside empty initial adjlist
data = [['0','1'],['2','1'],['0','2'],['1','3']]
for line in data: #for loop for appending into adjacency list the correct indices taken from out of the edgelist
#(this line won't be needed when hardcoding input) line = line.replace("\n","").split(" ")
for values in line:
values_as_int = int(values)
edgelist.append(values_as_int)
#set of vertices present in this file - pick out only n vertices
verticesset=set(edgelist)
listofusefulvertices=list(verticesset)[0:n]
P = list(itertools.permutations(listofusefulvertices,2))
x.append(edgelist[0::2])
y.append(edgelist[1::2])
x = sum(x,[])
y = sum(y,[])
dataint=zip(x,y)
datatuples=list(dataint)
outdata = set(datatuples)&set(P)
output=list(outdata)
for k in range(len(output)):
edge_i.append(output[k][0])
edge_i.append(output[k][1])
edge_j.append(output[k][1])
edge_j.append(output[k][0])
for i in range(len(edge_i)):
u = edge_i[i]
v = edge_j[i]
adjlist[u].append(v)
print(adjlist)
tree = []
for vertexNum in range(len(listofusefulvertices)):
tree.append([])
treeVertices = [0]*n
treeVertices[0]=1
for vertex in range(0,n): #(here the range in skeletal code from school used 1,n but it only worked for me when I used 0,n-1 or 0,n)
if treeVertices[vertex] == 1:
for adjVertex in adjlist[vertex]:
if treeVertices[adjVertex] == 0:
treeVertices[adjVertex]=1
tree[adjVertex].append(vertex)
tree[vertex].append(adjVertex)
print(tree)
#The data from files were: file 1: [['0','1'],['2','1'],['0','2'],['1','3']]
# file 2: [['10','2'],['7','4'],['11','3'],['1','12'],['6','8'],['10','3'],['4','9'],['5','7'],['8','12'],['2','11'],['1','6'],['0','10'],['7','2'],['12','5']]
我没有仔细阅读你的代码,你真的应该看看指南Minimal, complete, verifiable example。在
然而,将一个边列表转换成一个图,然后使用标准的
mst
算法,例如Prim的:一个图可能有多个有效的MST,例如,较小的},这也是一个有效的MST,但与预期的输出不同。在
edgelist
生成{问题出在最后的主处理循环中。使用节点0作为起始节点,但是假设连接按数字顺序运行。标记与节点0相邻的所有节点(仅标记节点10),然后占用节点1。还没有连接,所以你跳过它。。。但你再也回不来了。在
下面是我的低技术调试运行的代码和跟踪:
输出:
^{pr2}$看到问题了吗?该算法假定,如果从可用节点移动到编号较高的节点,则查找生成树的流程将始终成功。因为这棵树需要几次“向下”移动,所以你并不能全部完成。从0开始,标记10,然后跳过节点1-9。当达到10时,添加节点2和3。。。但你再也不会回去扩大他们,这就是你所能得到的。在
要想得到所有这些,请执行以下两种操作之一:
这能让你找到解决办法吗?在
我想我可以通过在for-vertex循环上方添加外循环
while all(treeVertices) == 0:
来修复它。现在对于file2长列表中的n=13,我得到这样的输出:[[10], [12, 6], [10, 11, 7], [10], [7, 9], [7, 12], [1], [2, 5, 4], [12], [4], [0, 3, 2], [2], [5, 1, 8]]
我不明白的是,为什么while any(treeVertices) == 0:
不能工作,它必须是all()?我想当treeVertices列表被1部分填充时,它不会包含“all”零,而是“any”0,应该会再次将迭代器发送回它的循环中。我在python中遇到过多个编码实例,其中any()和all()的用法对我产生了相反的影响,any()的作用类似于all(),all()的作用类似于any()。知道为什么吗?在相关问题 更多 >
编程相关推荐