Python中的邻接矩阵

Question

Python中的邻接矩阵

16

我无法找到任何关于如何在Python中创建带权重的邻接矩阵的清晰解释。我认为创建应该是相对简单的。

我有以下矩阵...

   1   2   3   4   5   6
1  0   15  0   7   10  0
2  15  0   9   11  0   9
3  0   9   0   0   12  7
4  7   11  0   0   8   14
5  10  0   12  8   0   8
6  0   9   7   14  8   0

数字1到6是顶点，括号内的数字是每个相邻顶点之间的权重。例如，边1-2的权重为15。

我该如何在Python中实现这个？我只需要一个简单的示例，不一定要使用我提供的示例。

我知道如何创建邻接表...

graph = {'1': [{'2':'15'}, {'4':'7'}, {'5':'10'}],
    '2': [{'3':'9'}, {'4':'11'}, {'6':'9'}],
    '3': [{'5':'12'}, {'6':'7'}],
    '4': [{'5':'8'}, {'6':'14'}],
    '5': [{'6':'8'}]}

但我需要一个邻接矩阵。

- buydadip

3

你听说过 networkx 吗？它是一个Python库，用于创建、操作和研究复杂网络。 - abcd

1

你必须使用基本的Python吗？你可以使用像numpy/scipy或networkx这样实现这些功能的库吗？ - smci

5个回答

7

我喜欢在Python中使用元组作为2D结构的键。

{(1, 1): 0, (3, 2): 9... }

我认为这种方法在概念上最清晰，因为它省去了上述解决方案中的中间数据结构。然而，如果您打算按行或列访问您的结构，则该中间数据结构--内部列表或行/列--可能会有用。

 for x, row in enumerated(matrix, 1):
       # process whole row 
       for y in enumerate(row, 1):
             # process cell...

如果单元格数据访问是您所专注的领域，下面的方法表达简单易懂，难以被超越：

for (x, y), value in matrix.iteritems():
      # act on cell

如果需要的话，可以对其进行排序。

 # (1, 1), (1, 2)...
 for (x, y), value in sorted(matrix.iteritems()):
       # act on cell

- jwilner

4

我不明白为什么这个被点踩了。它看起来是一个有用的选项。有什么理由需要避免使用它吗？ - SystemParadox

4

这将把您的“邻接列表”（实际上是一个字典，而不是一个列表）转换为真正的矩阵：

import networkx as nx

graph = {'1': [{'2':'15'}, {'4':'7'}, {'5':'10'}],
    '2': [{'3':'9'}, {'4':'11'}, {'6':'9'}],
    '3': [{'5':'12'}, {'6':'7'}],
    '4': [{'5':'8'}, {'6':'14'}],
    '5': [{'6':'8'}]}
new_graph = nx.Graph()
for source, targets in graph.iteritems():
    for inner_dict in targets:
        assert len(inner_dict) == 1
        new_graph.add_edge(int(source) - 1, int(inner_dict.keys()[0]) - 1,
                           weight=inner_dict.values()[0])
adjacency_matrix = nx.adjacency_matrix(new_graph)

你的图形(graph)格式不是特别适合在networkx中使用。 networkx支持对图形及其邻接矩阵进行各种操作，因此以这种格式拥有图形应该非常有帮助。请注意，我已将您的图形移动到使用Python索引(即从0开始)。

In [21]: adjacency_matrix
Out[21]: 
matrix([[  0.,  15.,   0.,   7.,  10.,   0.],
        [ 15.,   0.,   9.,  11.,   0.,   9.],
        [  0.,   9.,   0.,   0.,  12.,   7.],
        [  7.,  11.,   0.,   0.,   8.,  14.],
        [ 10.,   0.,  12.,   8.,   0.,   8.],
        [  0.,   9.,   7.,  14.,   8.,   0.]])

- abcd

2

不使用第三方库，用本地的 Python 实现会更有帮助。 - NinjaGaiden

4

如之前所提到的，Python中处理矩阵的标准方法是使用NumPy。以下是一个函数，它仅从邻接表中读取邻接矩阵。（节点的隐式顺序通过参数nodes变得显式。）

import numpy

def weighted_adjmatrix(adjlist, nodes):
    '''Returns a (weighted) adjacency matrix as a NumPy array.'''
    matrix = []
    for node in nodes:
        weights = {endnode:int(weight)
                   for w in adjlist.get(node, {})
                   for endnode, weight in w.items()}
        matrix.append([weights.get(endnode, 0) for endnode in nodes])
    matrix = numpy.array(matrix)
    return matrix + matrix.transpose()

在这种情况下，weighted_adjmatrix(graph, nodes=list('123456'))会返回NumPy数组。

array([[ 0, 15,  0,  7, 10,  0],
       [15,  0,  9, 11,  0,  9],
       [ 0,  9,  0,  0, 12,  7],
       [ 7, 11,  0,  0,  8, 14],
       [10,  0, 12,  8,  0,  8],
       [ 0,  9,  7, 14,  8,  0]])

如果想要一个常规列表，可以调用tolist()方法。

- egnha

-1

#Graph using adjacency matrix
class GraphAM:
    #no of vertices
    __n=0
    #adjacency matrix of size 10x10 initialize with 0
    __g=[[0 for column in range(10)]for row in range(10)]
    __listofVertex=[]

    def __init__(self,vertex):
        #adding a vertex in a list 
        self.__listofVertex.append(vertex)
        #saving no of vertices
        self.__n=len(self.__listofVertex)
        #updating the adjacency matrix --> NxN matrix for row and column 0
        for source in range(0, self.__n):
            for destination in range(0, self.__n):
                self.__g[source][destination]= 0
    
    def add_vertex(self,source,destination):
        #intialize source Index and destination index with 0
        indexS=0
        indexD=0
        #check if source vertex available in list  __listofVertex, if not present then add it
        if source in self.__listofVertex:
            indexS=self.__listofVertex.index(source)
        else:
            print("Vertex {0} not present in Graph, adding it automatically.".format(source))
            self.__listofVertex.append(source)
            indexS=self.__listofVertex.index(source)
            #addition of vertex done so increment the count of vertex   
            self.__n = self.__n + 1
            
        #check if destination vertex available in list  __listofVertex, if not present then add it   
        if destination in self.__listofVertex:
            indexD=self.__listofVertex.index(destination)
        else:
            print("Vertex {0} not present in Graph, adding it automatically.".format(destination))
            self.__listofVertex.append(destination)
            indexD=self.__listofVertex.index(destination)
            #addition of vertex done so increment the count of vertex   
            self.__n = self.__n + 1
    
        if(indexS>= self.__n) or (indexD >= self.__n):
            print("One of the vertex doesn't exists !")
            
        if self.__n > 1:
            for i in range(0, self.__n):
                self.__g[i][self.__n-1]= 0
                self.__g[self.__n-1][i]= 0

            
    def add_edge(self,source,destination):
        #intialize source Index and destination index with 0
        indexS=0
        indexD=0
        if source in self.__listofVertex:
            indexS=self.__listofVertex.index(source)
        else:
            print("Cannot be included in the graph ,  Add the vertex {0}".format(source))
            
        if destination in self.__listofVertex:
            indexD=self.__listofVertex.index(destination)
        else:
            print("Cannot be included in the graph ,  Add the vertex {0}".format(destination))
            
        if (indexS >0 and indexS == indexD):
            print("Same Source and Destination")
        else:
            self.__g[indexS][indexD]= 1
            self.__g[indexD][indexS]= 1 
    
    def removeVertex(self, location):
        indexL=0
        if location in self.__listofVertex:
            #get location index in the list
            indexL=self.__listofVertex.index(location)
            while(indexL < self.__n ):
                for i in range(0, self.__n):
                       self.__g[i][indexL]= self.__g[i][indexL + 1]
                
                for i in range(0, self.__n):
                       self.__g[indexL][i]= self.__g[indexL + 1][i]
                indexL = indexL + 1
                
            self.__n = self.__n -1
            self.__listofVertex.remove(location)
            print("Successfully removed {0} from graph,current list of vertex are below :\n  {1} ".format(location,self.__listofVertex))
        else:
            print("No such vertex exist in the graph")
        
    def print_graph(self):
        print("\n")
        for i in range(len(self.__listofVertex)):
            print("\t\t", self.__listofVertex[i],end ="")
        for i in range(0, self.__n):
            print("\n",self.__listofVertex[i],end="  ")
            for j in range(0, self.__n):
                print("\t\t", self.__g[i][j], end ="")
                
        print("\n")
            


g1=GraphAM("MUM")
g1.add_vertex("MUM","DL")
g1.add_vertex("DL","KOL")
g1.add_vertex("HYD","BLR")
g1.add_vertex("CHN","KOL")
g1.add_vertex("HYD","GHY")
g1.add_edge("MUM","DL")
g1.add_edge("DL","KOL")
g1.add_edge("HYD","BLR")
g1.add_edge("CHN","KOL")
g1.add_edge("HYD","GHY")
g1.print_graph()
g1.removeVertex("KOL")
g1.print_graph()

- Arijit Gupta

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- enpenax · Accepted Answer

我认为最常见和最简单的邻接矩阵存储概念是使用二维数组，而在Python中则对应于嵌套列表。

mat = [[0, 15, 0, 7, 10, 0], [15, 0, ...], [...], [...]]
m[0][1]  # = 15 (weight of 1-2)

如果值是只读的，您可以使用嵌套元组代替:)

当然，您可以尽情发挥，使用字典或编写一个类并重新定义__getattr__，以在访问时间和存储方面更加高效，因为矩阵是对称的。