如何在数据结构中表示一个奇怪的图形
一种简单的表示图的方法是使用这样的数据结构：
{1:[2,3],
2:[1,3],
3:[1,2]}
在这个字典中，键是节点，而边则用一个列表来表示与之相连的其他节点。如果这些连接不是对称的，这个数据结构也可以很容易地表示一个有向图：
{1:[2],
2:[3],
3:[1]}
我对图论了解不多，所以我接下来要提的可能已经有简单的解决方案，但我不知道该找什么。我遇到了一种情况，我认为这个图在某种程度上是有向的，这取决于你所在的节点和你来自的节点。为了说明这一点，我有一张图：
想象一下，你在边A上开着卡丁车飞驰，当你到达节点1时，向左转到边B。因为你开得太快，当你到达节点3时，你被迫继续走边F。然而，如果你是从边F过来的，你就可以选择走边E或边B。很明显，节点3与节点1和节点2是相连的，但你能否从节点3到达它们，取决于你是从哪个方向来的。
我想知道是否有图论的概念可以描述这种情况，或者是否有简单的数据结构可以用来表示它。虽然我会用Python来写我的代码，但我会接受任何适用语言的建议。
编辑： 我试着上传一张图片来配合这个内容，但我不确定它是否显示出来。如果没有，这里有一个链接到图片
编辑2： 我应该更清楚一点。发布的图片是一个完整图的一部分，实际上在A、D和F的屏幕外还有更多的节点。
3 个回答
把你的图用字符串映射到字符串再映射到集合的方式来表示。
更具体一点，在Python中你可以这样写：
graph = {
'A': {
'B': set(['C', 'D', ...]),
'E': set(['F']),
},
...
}
如果在graph这个映射中，A的条目包含了B这个键，那么A和B之间就存在一条边。
这条边可以被走动，如果我们出发的节点在graph['A']['B']映射到的集合中。
下面这个Python类实现了这个规范（你可以在这个链接找到带注释的版本）：
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方法就可以了。
你可以把它做成一个简单的图，里面有节点和边。在每个节点里，存一个边的列表。对于每一条边，记录从这个“入口”边到有效的出口边的对应关系。
我得提醒你，你发的图片其实不是一个图，因为A、F和D这些点没有连接到任何节点（除非它们在屏幕外面）。
