從python中的矩陣創建鄰接列表圖表

所以我試圖從字母矩陣中製作一個字母（代表一個麻煩牌）的圖形。所以說，我有這樣的：從python中的矩陣創建鄰接列表圖表

[ [ A, B, C, D], 
    [E, F, G, H], 
    [I, J, K, L], 
    [M, N, O, P] ].

我希望每個節點是一封信，但我有麻煩找出如何讓每個節點的鄰居。例如，節點A將具有鄰居B，E和F.雖然節點K將具有鄰居F，G，H，J，L，M，O和P.任何幫助將不勝感激！

來源

2016-08-05 ayc.19

如果你正在談論[圖表在python]（http://www.python-course.eu/graphs_python.php）你應該改變你的方法。 – bhansa

你可以遍歷您的矩陣中的每個節點，然後在右&下面添加到結果每個相鄰節點：

matrix = [ 
    ['A', 'B', 'C', 'D'], 
    ['E', 'F', 'G', 'H'], 
    ['I', 'J', 'K', 'L'], 
    ['M', 'N', 'O', 'P'] 
] 

def add(adj_list, a, b): 
    adj_list.setdefault(a, []).append(b) 
    adj_list.setdefault(b, []).append(a) 

adj_list = {} 
for i in range(len(matrix)): 
    for j in range(len(matrix[i])): 
     if j < len(matrix[i]) - 1: 
      add(adj_list, matrix[i][j], matrix[i][j+1]) 
     if i < len(matrix[i]) - 1: 
      for x in range(max(0, j - 1), min(len(matrix[i+1]), j+2)): 
       add(adj_list, matrix[i][j], matrix[i+1][x]) 

import pprint 
pprint.pprint(adj_list)

輸出：

{'A': ['B', 'E', 'F'], 
'B': ['A', 'C', 'E', 'F', 'G'], 
'C': ['B', 'D', 'F', 'G', 'H'], 
'D': ['C', 'G', 'H'], 
'E': ['A', 'B', 'F', 'I', 'J'], 
'F': ['A', 'B', 'C', 'E', 'G', 'I', 'J', 'K'], 
'G': ['B', 'C', 'D', 'F', 'H', 'J', 'K', 'L'], 
'H': ['C', 'D', 'G', 'K', 'L'], 
'I': ['E', 'F', 'J', 'M', 'N'], 
'J': ['E', 'F', 'G', 'I', 'K', 'M', 'N', 'O'], 
'K': ['F', 'G', 'H', 'J', 'L', 'N', 'O', 'P'], 
'L': ['G', 'H', 'K', 'O', 'P'], 
'M': ['I', 'J', 'N'], 
'N': ['I', 'J', 'K', 'M', 'O'], 
'O': ['J', 'K', 'L', 'N', 'P'], 
'P': ['K', 'L', 'O']}

來源

2016-08-05 08:24:33 niemmi

你必須使用字典存儲連接到節點的節點：

g = { "A" : ["D", "F"], 
     "B" : ["C"], 
     "C" : ["B", "C", "D", "E"], 
     "D" : ["A", "C"], 
     "E" : ["C"], 
     "F" : ["D"] 
    }

取決於你圖的結構。

獲取一個節點的鄰居在上圖可以簡單地訪問節點的值

>>> g["A"] 
>>> ["D","F"]

來源

2016-08-05 06:51:54 bhansa

假設你的矩陣是n×m的矩陣，每個元素都是一個獨特字符串類似如下：


    # The matrix 

matrix = [ 
    ['A', 'B', 'C', 'D'], 
    ['E', 'F', 'G', 'H'], 
    ['I', 'J', 'K', 'L'], 
    ['M', 'N', 'O', 'P'] 
]

您可以先定位元素的索引：


    node = 'K' # Input 

    # Get the matrix dimension 
    n = len(matrix) 
    m = len(matrix[0]) 

    # Assume there is exactly one matching node 
    for i in xrange(n): 
     for j in xrange(m): 
      if matrix[i][j] == node: 
       x, y = i, j

，然後返回鄰國的列表：

 
    # Get the (at most) 8 neighbors 

    neighbors = [row[max(0,y-1):y+2] for row in matrix[max(0,x-1):x+2]] 
    answer = set([v for r in neighbors for v in r]) 
    answer.remove(node) 
    answer = list(answer)

如果該節點可以有多次出現，見How to find the index of a value in 2d array in Python?另外，如果你是新來的Python這些鏈接可能對您有用：

來源

2016-08-05 07:33:54

從python中的矩陣創建鄰接列表圖表

回答

相關問題