python上的生成树

Question

我有这个硬件：

1. 从文件中读取边缘列表
2. 把它变成一个邻接列表
3. 输出图的一个未加权的无向生成树（我们可以假设起点在顶点0）

我得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']]

Answer 1

问题出在最后的主处理循环中。使用节点0作为起始节点，但是假设连接按数字顺序运行。标记与节点0相邻的所有节点（仅标记节点10），然后占用节点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)
    print ("Working on vertex", vertex, treeVertices[vertex] == 1)
    if treeVertices[vertex] == 1:
        for adjVertex in adjlist[vertex]:
            print ("  Adjacent vertex", adjVertex, treeVertices[adjVertex] == 0)
            if treeVertices[adjVertex] == 0:
                treeVertices[adjVertex]=1
                tree[adjVertex].append(vertex)
                tree[vertex].append(adjVertex)

print("Spanning tree", tree)

输出：

^{pr2}$

看到问题了吗？该算法假定，如果从可用节点移动到编号较高的节点，则查找生成树的流程将始终成功。因为这棵树需要几次“向下”移动，所以你并不能全部完成。从0开始，标记10，然后跳过节点1-9。当达到10时，添加节点2和3。。。但你再也不会回去扩大他们，这就是你所能得到的。在

要想得到所有这些，请执行以下两种操作之一：

1. 将“未展开”节点放在“待办事项”列表中，从[0]开始。直到你的列表变为空。在
2. 保留当前结构，但添加一个外部循环，该循环将一直持续到标记所有节点或未添加任何边（找不到生成树）。在

这能让你找到解决办法吗？在