回答此问题可获得 20 贡献值,回答如果被采纳可获得 50 分。
<p>我有这个硬件:</p>
<ol>
<li>从文件中读取边缘列表</li>
<li>把它变成一个邻接列表</li>
<li>输出图的一个未加权的无向生成树(我们可以假设起点在顶点0)</li>
</ol>
<p>我得3分有问题。正确输出。也就是说,文件1应该输出<code>[[1],[0,2,3],[1],[1]]</code>,我得到了<code>[[1,2],[0,3],[0],[1]]</code>,这有点正常,因为它们都是来自文件1的<code>n=4</code>的生成树</p>
<p>但主要的问题是:对于文件2,我不知道我的代码有什么问题:我得到:<code>[[10], [], [10], [10], [], [], [], [], [], [], [0, 3, 2], [], []]</code></p>
<p>代码末尾的文件的数据。
(编辑:从<code>tree=[]</code>开始是问题所在,其余的没有问题)</p>
<p>下面是我对这个问题的尝试:</p>
<pre><code>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 <a href="https://www.cnpython.com/list/append" class="inner-link">append</a>ing 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']]
</code></pre>