파이썬의 행렬에서 인접 목록 그래프 만들기

Question

그래서 글자 매트릭스에서 글씨 그래프 (boggle 보드를 나타 내기 위해)를 만들려고합니다. 그래서 같은 것을 가지고 말 : 나는 각 노드는 편지가되고 싶어요

[ [ 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를 가질 것입니다.

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

그래프의 구조에 따라 :

Answer 1

그런 다음 매트릭스의 모든 노드를 통해 루프는 결과에 아래를 잘 &에서 모든 이웃 노드를 추가 할 수 있습니다

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']} 

Answer 2

당신은 노드 에 연결된 노드를 저장하기 위해 사전을 사용해야합니다.

는 단순히

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

Answer 3

당신의 매트릭스를 가정 것은 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?를 참조 파이썬을 처음 사용하는 경우 이러한 링크는 당신을 위해 유용 할 수 있습니다 :

• Sub matrix of a list of lists (without numpy)
• Convert multi-dimensional list to a 1D list in Python
• How to find the index of a value in 2d array in Python?