将树转换为矩阵Python 3

Question

我试图将树：（列表Nat（listof树））列表转换为图矩阵，但我不知道从哪里开始。我不是在寻找代码，但更多的是如何解决这个问题的想法。

例如，树是

aTree = [3 , [ 
      [1 , []] , 
      [0 , [ 
        [2 , []] , 
        [5 , []] 
        ] 
      ] , 
      [4 , []] 
      ] 
     ] 

这将是这样的：

 3 
    /| \ 
    1 0 4 
    /\ 
    2 5 

和矩阵将

aM = 

    [[0 , 0 , 1 , 1 , 0 , 1] , 
    [0 , 0 , 0 , 1 , 0 , 0] , 
    [1 , 0 , 0 , 0 , 0 , 0] , 
    [1 , 1 , 0 , 0 , 1 , 0] , 
    [0 , 0 , 0 , 1 , 0 , 0] , 
    [1 , 0 , 0 , 0 , 0 , 0]] 

功能将treetomatrix(Tree, N)其中N是树中顶点的数量。所以treetomatrix(aTree, 6) => aM。

任何建议将不胜感激。

Answer 1

这个问题的真正困难的部分是如何改变你使用的怪异列表结构到字典中。 （如果你不知道字典，请阅读它们，他们会尽力让你的名单做到，但更自然。）我暂时忽略了这一点，接下来会做。

aTree = {3 : { 
       1: {}, 
       0:{ 2: {}, 
        5: {} 
       } 
       4:{} 
      } 
     } 

def tree_to_matrix(tree, n): 
    return tree_to_mat(tree, [[0 for i in range(n)] for j in range(n)]) 

def tree_to_mat(tree, mat): 
    for k, v in tree.items(): 
     for i in v.keys(): 
      mat[i][k] = mat[k][i] = 1 
     mat = tree_to_mat(v, mat) 
    return mat 

print(tree_to_matrix(aTree, 6)) 

打印

[[0, 0, 1, 1, 0, 1], [0, 0, 0, 1, 0, 0], [1, 0, 0, 0, 0, 0], [1, 1, 0, 0, 1, 0], [0, 0, 0, 1, 0, 0], [1, 0, 0, 0, 0, 0]] 

这是我们所期望的输出。您可能会发现将输入读入自定义Tree类更容易，然后编写该类的方法来生成矩阵。诀窍是使用递归，并意识到您必须同时设置mat[i][k]和mat[k][i]。

编辑：这是我的哈克方式将您的列表变成字典。

def dictify(l): 
    return {l[0]: d_helper(l[1])} 

def d_helper(l): 
    d={} 
    for i in l: 
     d.update(dictify(i)) 
    return d 

dictify(aTree) 

还有一个更好的方法，但是这个工作。