如何表示在一些數據結構的奇怪圖表

一種簡單的方式來表示的曲線圖是與以下形式的數據結構：如何表示在一些數據結構的奇怪圖表

{1:[2,3], 
2:[1,3], 
3:[1,2]}

凡在此字典中的鍵是節點，並且邊緣被表示通過它們連接到的其他節點的列表。此數據結構也可以很簡單地表示有向圖，如果鏈接是不對稱的：

{1:[2], 
2:[3], 
3:[1]}

我不知道很多關於圖形理論，所以我很擔心提出可能已經有一個簡單的解決方案，但我不知道要尋找什麼。我已經遇到了我認爲的一種情況，即一個圖形有點指向，取決於您所在的節點以及您來自哪個節點。爲了說明這一點，我有一個圖紙：

Strangely Directional Graph

想象一下你在卡丁車沿着邊緣一輛飛馳，並在節點1你掛左轉進入邊緣B.既然你如此之快，當你擊中節點3時，你不得不繼續到邊F.然而，如果你來自邊F，你可以繼續到邊E或B.很明顯，節點3連接到1和2，但是否可以從該節點到達它們取決於您來自哪個方向。

我想知道是否有一個圖論的概念，描述這個和/或是否有一個簡單的數據結構來描述它。雖然我會用python編寫我的代碼，但我會接受來自任何合理適用語言的建議。

編輯：我試圖張貼一個圖像去與此，但我不知道它是否顯示出來。如果這裏不是鏈接image

編輯2：我應該清楚。發佈的圖像意味着是完整圖形的一部分，其中A，D和F的屏幕外有更多節點。

來源

2011-06-16 Wilduck

這可以用directed graph表示。

圖中的節點可以表示爲圖中的兩個節點。將節點想象成代表街道特定位置的位置 - 邊緣就像入站和出站車道。

enter image description here

來源

2011-06-16 18:16:53 unutbu

我不認爲這就是我要找的。每個節點只根據你來自哪裏而定向。如果這是我在這種情況下尋找的東西，能否更好地解釋它是如何應用的？ – Wilduck 2011-06-16 18:18:50

另外，我試圖張貼一個插圖。它顯示了嗎？ – Wilduck 2011-06-16 18:19:08

這個問題表明它不是有向圖。邊的方向取決於您剛通過的節點。 – mwcz 2011-06-16 18:19:59

您可以實現它作爲節點和邊緣的基本圖形。在每個節點中存儲邊緣列表。對於每個邊，存儲從該「入口」邊緣到有效出口邊緣的映射。

我應該指出你發佈的圖片不是圖形，因爲A，F和D不能連接到任何節點（除非它們只是在屏幕外）。

來源

2011-06-16 18:28:27 mwcz

我想我應該是明確的，但是，是的，我試圖暗示有更多的節點在屏幕外。 – Wilduck 2011-06-16 18:32:04

將您的圖表示爲字符串映射到字符串映射到集合的映射。

更清晰，在Python中，你將有：如果密鑰B通過在映射條目A包含A和B之間存在

graph = { 
    'A': { 
     'B': set(['C', 'D', ...]), 
     'E': set(['F']), 
    }, 
    ... 
}

邊緣。

如果我們來自的節點包含在由graph['A']['B']映射到的集合中，則可以走此邊。

下面的Python類實現此規範（你可以找到this gist一個註釋版本）：

class Graph(object): 
    def __init__(self): 
     self.nodes = {} 

    def addEdge(self, (node1, comingFrom1), (node2, comingFrom2)): 
     self.nodes.setdefault(node1, {})[node2] = comingFrom1 
     self.nodes.setdefault(node2, {})[node1] = comingFrom2 

    def isEdge(self, comingFrom, passingBy, goingTo): 
     try: 
      return comingFrom in self.nodes[passingBy][goingTo] 
     except KeyError: 
      return False 

    def destinations(self, comingFrom, passingBy): 
     dests = set() 
     try: 
      for node, directions in self.nodes[passingBy].iteritems(): 
       if comingFrom in directions: 
        dests.add(node) 
     except KeyError: 
      pass 

     return dests 

    def sources(self, passingBy, goingTo): 
     return self.destinations(goingTo, passingBy)

這個類可以這樣使用：

>>> graph = Graph() 
>>> graph.addEdge(('0', set([  ])), ('1', set(['3', '2']))) 
>>> graph.addEdge(('1', set(['0'  ])), ('3', set(['4'  ]))) 
>>> graph.addEdge(('1', set(['0'  ])), ('2', set(['5'  ]))) 
>>> graph.addEdge(('3', set(['1', '2'])), ('4', set([  ]))) 
>>> graph.addEdge(('3', set(['4'  ])), ('2', set(['5'  ]))) 
>>> graph.addEdge(('2', set(['1', '3'])), ('5', set([  ]))) 

>>> print graph.isEdge('0', '1', '3') 
True 
>>> print graph.isEdge('1', '3', '2') 
False 
>>> print graph.isEdge('1', '2', '5') 
True 
>>> print graph.isEdge('5', '2', '3') 
True 
>>> print graph.isEdge('3', '2', '5') 
True 

>>> print graph.destinations('0', '1') 
set(['3', '2']) 
>>> print graph.destinations('1', '3') 
set(['4']) 
>>> print graph.destinations('3', '4') 
set([]) 

>>> print graph.sources('0', '1') 
set([]) 
>>> print graph.sources('1', '3') 
set(['0']) 
>>> print graph.sources('3', '4')

所選擇的數據結構和它們的用法已經允許構建有向圖，只需要調整addEdge方法。

來源

2011-06-16 19:42:30 GaretJax

如何表示在一些數據結構的奇怪圖表

回答

相關問題