Python 中的邻接矩阵
Adjacency matrix in Python
关于如何在考虑权重的情况下在 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'}]}
但是我需要一个邻接矩阵。
我认为存储邻接矩阵最常见和最简单的概念是使用二维数组，在python中对应于嵌套列表
mat = [[0, 15, 0, 7, 10, 0], [15, 0, ...], [...], [...]]
m[0][1] # = 15 (weight of 1-2)
如果值是只读的，您可以使用嵌套元组代替:)
当然，您可以随心所欲地使用字典或编写 class 并重新定义 __getattr__ 以提高访问时间和存储效率，因为矩阵是对称的。
我喜欢 python 中这样的二维结构的元组键。
{(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
这会将您的 "adjacency list"（实际上是字典，而不是列表）转换为真正的矩阵：
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.]])
如前所述，在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()。
#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()
关于如何在考虑权重的情况下在 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'}]}
但是我需要一个邻接矩阵。
我认为存储邻接矩阵最常见和最简单的概念是使用二维数组，在python中对应于嵌套列表
mat = [[0, 15, 0, 7, 10, 0], [15, 0, ...], [...], [...]]
m[0][1] # = 15 (weight of 1-2)
如果值是只读的，您可以使用嵌套元组代替:)
当然，您可以随心所欲地使用字典或编写 class 并重新定义 __getattr__ 以提高访问时间和存储效率，因为矩阵是对称的。
我喜欢 python 中这样的二维结构的元组键。
{(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
这会将您的 "adjacency list"（实际上是字典，而不是列表）转换为真正的矩阵：
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.]])
如前所述，在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()。
#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()