使用嵌套字典來存儲用戶定義的圖

我想讓用戶手動輸入圖形，而不是在代碼中使用它'預先存在'，用於我的Dijkstra算法。使用嵌套字典來存儲用戶定義的圖

我已經做到了這一點，但希望對其實現和用戶友好性提供一些反饋意見。此外，還有一種將圖形輸入嵌套字典的更有效方法嗎？如果是這樣怎麼樣？

大約代碼要點

數據必須使用嵌套的字典
環路將被存儲在零例如BB的0不留爲空白，但是這僅在一個循環中存在的用戶圖形發生否則忽略。
理想我不希望使用現有的庫裏面什麼編碼它自己之前更好地瞭解發生了什麼

千恩萬謝。編輯：不再需要重複需求。

{'A': {'C': 1, 'B': 5}, 'D': {}, 'B': {'D': 2}, 'C': {'D': 9}}

^節點的期望輸出也是當前輸出。

nodes = {} 


def add_node(): 
    entered_graph = False 
    while not entered_graph: 
     source_node = input("Enter a source node: ") 
     num_neighbours = int(input("Enter how many neighbours this node has" 
            "including previously entered nodes: ")) 
     nodes[source_node] = {} 
     for neighbour in range(num_neighbours): 
      neighbour = input("Enter neighbor node: ") 
      distance = int(input("Enter distance from source node to this neighbor node: ")) 
      nodes[source_node][neighbour] = distance 
     end_loop = input("Enter y to finish graph entry: ") 
     end_loop = end_loop.lower() 
     if end_loop == "y": 
      entered_graph = True 

add_node() 
print(nodes)

來源

2016-10-18 Padwas

「數據必須使用嵌套字典存儲」爲什麼？我將創建一個元組作爲關鍵字'（from_location_id，to_location_id）'的字典。 – roganjosh

特別是如果你說這是一個對稱圖，例如a - > b == b - > a。那麼你只需要存儲這些對中的一個並測試兩者即（a，b）或（b，a）。就內存方面的重大問題而言，這將非常重要。以單一位置爲嵌套的嵌套字典會導致大量重複，這是不必要的。 – roganjosh

事實上，我已經在我的算法中糾正了這個問題，所以現在不需要兩次添加每個弧。 – Padwas

你真的只希望用戶輸入一次邊緣，然後你可以只存儲兩次。

edges = {} 
while True: 
    edge = input('Enter an edge as Node names separated by a space followed by a number ("exit" to exit): ') 
    if edge == 'exit': 
     break 
    node1, node2, weight = edge.split() 
    weight = float(weight) 
    if node1 not in edges: 
     edges[node1] = {} 
    if node2 not in edges: 
     edges[node2] = {} 
    edges[node1][node2] = weight 
    edges[node2][node1] = weight

用戶輸入每條邊一次作爲"A B 3.5"

來源

2016-10-18 15:53:15

Khanacademy有不同的方式來表示圖形相當不錯的頁面。

對於無向圖（a => b和b => a），我會親自看看使用邊列表。它可以進行排序以提高查找效率，並且比其他方法（如鄰接表）更有效地提高內存效率

來源

2016-10-18 15:55:27 Aaron

在源代碼中，您可能更加模塊化，因爲在「add_node」中應該只添加一個節點。我認爲進入立即用在一個線路費用所有的鄰居會更人性化，所以使用你堅持的數據結構：

from itertools import tee   #For pairwise iteration 
from collection import defaultdict #To add arcs to non-existing nodes 

def add_node(graph): 
    source = input("Please enter node ('quit' to stop):") 
    if node == 'quit': return False 
    for neighbor,dist in zip(tee(input("Please enter neighbors [neighbor distance neighbor distance ...]").split())): 
     graph[source][neighbor] = int(dist) 
     graph[neighbor][source] = int(dist) 
    return True 

def add_graph(self): 
    graph = defaultdict(dict) 
    while add_node(graph): pass 

print add_graph()

的defaultdict節省您的檢查，我想輸入這樣更容易，而不是鄰居由鄰居。您甚至可以使[源鄰居的相鄰成本近鄰成本...] - [源...] - ...爲單行輸入。

如果您堅持不讓課程脫離這個層次，那麼模塊化可以更容易地將代碼添加到「圖表」或「節點」。

來源

2016-10-18 16:02:03 kabanus

使用嵌套字典來存儲用戶定義的圖

回答

相關問題