在Python中表示网络

Question

我有一些顶点，比如说 dic = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'n':6, 'm':7, 'g':8}，还有两列数据，表示这些顶点之间的关系：

a a
b d
e f
c f
n f
m g

我想把第一列中的每个顶点和第二列中对应的顶点通过一条边连接起来。比如说，a 和 a 之间的连接表示一个循环。b 和 d 之间的连接是可以的。e、c 和 n 这几个顶点都共享同一个顶点 f。与其说 e 和 f 连接，c 和 f 连接，n 和 f 连接，不如说 e、c 和 n 都和 f 连接。

Answer 1

@kurosch的回答提到的邻接表的另一种常见替代方案叫做邻接矩阵。简单来说，邻接矩阵就是一个表格，用来表示所有可能的连接关系。在这个表格中，1表示有连接，0表示没有连接。

adj = [[0 for x in range(len(dic)] for x in range(len(dic))]
adj[dic['a'][dic['b']] = 1
etc..

Answer 2

请查看： https://www.python.org/doc/essays/graphs/

graph = {
    'a' : [ 'a' ],
    'b' : [ 'd' ],
    'c' : [ 'f' ],
    'd' : [],
    'e' : [ 'f' ],
    'f' : [],
    'g' : [],
    'm' : [ 'g' ],
    'n' : [ 'f' ]
}

print [ vertex for vertex, edges in graph.items() if 'f' in edges ]

编辑：

好的，听起来你只是想要一个函数来根据你给定的输入来构建图形，对吧？

像这样：

def build_graph( vertices, edges ):
    graph = dict( (v, list()) for v in vertices.keys() )
    for a, b in edges:
        graph[ a ].append( b )
    return graph

如果你需要帮助将你的列状数据解析成一对一的列表，那就完全是另一个问题了。