Python中的邻接表和邻接矩阵

Question

你好，我理解邻接表和邻接矩阵的概念，但我不清楚如何在Python中实现它们：

想要实现以下两个示例的算法，但并不知道初始输入，因为这些示例在代码中硬编码了输入：

对于邻接表：

    a, b, c, d, e, f, g, h = range(8) 
    N = [ 
     {b:2, c:1, d:3, e:9, f:4},    # a 
     {c:4, e:3},                   # b 
     {d:8},                        # c 
     {e:7},                        # d 
     {f:5},                        # e 
     {c:2, g:2, h:2},              # f 
     {f:1, h:6},                   # g 
     {f:9, g:8}                    # h 
   ] 

对于邻接矩阵：

    a, b, c, d, e, f, g, h = range(8) 
    _ = float('inf') 
    #     a b c d e f g h
    W = [[0,2,1,3,9,4,_,_], # a 
        [_,0,4,_,3,_,_,_], # b 
        [_,_,0,8,_,_,_,_], # c 
        [_,_,_,0,7,_,_,_], # d 
        [_,_,_,_,0,5,_,_], # e 
        [_,_,2,_,_,0,2,2], # f 
        [_,_,_,_,_,1,0,6], # g 
        [_,_,_,_,_,9,8,0]] # h

再次感谢任何帮助，非常感谢！

- Baraa

---

例如，我知道将会有一个输入来创建邻接表或矩阵，但我不知道这些输入将是什么，因此基本上为了拥有一个算法，每当我有顶点和边的输入时，就可以创建邻接表或矩阵... - Baraa

在邻接矩阵中，无穷大代表什么意思？ - Eric

那只是一个例子，当缺少一条边时，它会变成无穷大。你可以忽略它，认为它代表没有边。 - Baraa

好的，那么0代表什么？对我来说，似乎你把它们搞反了。 - Eric

零是代表身份的，我猜。但在某些图形中可能不适用，例如具有常规循环边的图形。这也可能会破坏一些简单算法（它们将无限循环而没有任何进展）。 - Blckknght

这是编程作业的一部分，我遇到的问题主要是邻接表，特别是因为我在用Python编程，如果是C++，我可以有一个数组，然后指向由边数连接的节点的指针，但我不确定如何在Python中实现。当涉及到邻接矩阵时，我觉得它更容易实现，因为它只是一个二维数组，输入是二维数组中的边数。 - Baraa

Answer 1

假设:

edges = [('a', 'b'), ('a', 'b'), ('a', 'c')]

这里有一些矩阵的代码:

from collections import defaultdict

matrix = defaultdict(int)
for edge in edges:
    matrix[edge] += 1

print matrix['a', 'b']

2

并且针对“列表”：

from collections import defaultdict

adj_list = defaultdict(lambda: defaultdict(lambda: 0))
for start, end in edges:
    adj_list[start][end] += 1

print adj_list['a']

{'c': 1, 'b': 2}

- Eric

---

你们两个提到了defaultdict，作为一个新手我不太确定它的确切含义，能否分享一些相关信息？感谢你们的示例，它们会有所帮助！ - Baraa

@user1748026 defaultdict 类型的工作方式与字典相同，但在设置时提供了“工厂函数”。然后，如果访问不存在的键，则它将调用工厂函数为该键创建默认值。 - Blckknght

@Eric：我喜欢你基于元组索引的矩阵解决方案。对于列表版本，你可以使用int作为内部defaultdict的工厂函数，而不是另一个lambda函数。 - Blckknght

Answer 2

设置数据结构可以非常简单。例如，可以使用defaultdict来实现邻接列表示例，如下所示：

from collections import defaultdict

N = defaultdict(dict)

然后当你开始获取输入时，只需为每个输入的边执行N[start][end] = weight。节点集可能会更加棘手，如果您有一些没有外向边缘的节点（您需要将内部字典的键与外部字典合并，以确保您拥有它们全部）。但是很多算法即使没有完整的节点列表也能正常工作。

邻接矩阵有点复杂，因为您需要知道节点数以便正确设置其维度。如果您事先知道它，那么就很容易：

number_of_nodes = 8
_ = float("inf")

N = [[_]*number_of_nodes for i in number_of_nodes]

如果您没有提供节点数量，您可能需要扫描输入的边缘以查找最高编号的节点，然后使用上面相同的代码来创建矩阵。例如，如果您的边缘是作为(start, end, weight) 3元组列表提供的，则可以使用以下代码：

number_of_nodes = max(max(start, end) for start, end, weight in edges)

- Blckknght

---

感谢您的输入，看来在使用Python编码时还有很多需要学习的地方，例如像这样编写代码：number_of_nodes = max(max(start, end) for start, end, weight in edges)。非常感谢您的建议，我会尝试使用您提供的一些方法！ - Baraa

当一些行缺失时（例如节点为1 2 5 6），这是否会创建邻接矩阵？这会创建一个6X6或4x4的矩阵吗？ - ubuntu_noob

Answer 3

希望下面的例子能够帮助您，它既有初始化图形，也有用户自定义。

class Graph:
"""
  Read the Intialized Graph and Create a Adjacency list out of it 
   There could be cases where in the initialized graph <map> link
  issues are not maintained
   for example node 2 to 1 link 
    2->1
   there needs to be a link then since undirected Graph
    1->2
"""

def __init__(self,Graph_init):
    self.edge={}
    for keys,values in Graph_init.items():
         for value in values:
             self.addEdge(keys,value);

"""
Add a vertex to graph map
structure is
int => int list
"""
def addVertex(self,v):
    if v not in self.edge:
        self.edge[v]=[]
"""
Add Edge from both vertex to each other
Make sure the nodes are present   

"""
def addEdge(self,u,v): if u not in self.edge: self.addVertex(u) if v not in self.edge: self.addVertex(v) if u not in self.edge[v]: self.edge[v].append(u) if v not in self.edge[u]: self.edge[u].append(v)

def isEdge(self,u,v):
    if u not in self.edge:
        return False
    if v not in self.edge:
        return False 
    return  u in self.edge[v] 

def display(self):
    for keys,values in self.edge.items():
        print(keys,":=>",values)

"""A initalized Graph (not in form of adjaceny list"""
Graph_init = {1:[2,3,5],
          2:[1,4],
          3:[1,6]};

"""Default constrcutor takes care of making the initialzed map to adjaceny 
list"""                 
g=Graph(Graph_init)
g.addVertex(1)
g.addVertex(2) 
g.addVertex(3)
g.addEdge(1,2)
g.addEdge(3,2)
g.display();

- Hariom Singh