图数据结构之邻接矩阵Adjacency Matrix(Python版)

        对于图这样的数据结构，我们在 图数据结构之字典实现(Python版) 有一种示例，可以表示出从起点出发有多少条路径选择，然后到达某个指定的终点，下面来看下另外一种图的数据结构。

邻接矩阵：顾名思义就是一个二维数组(矩阵)来保存顶点与相邻顶点之间的关系，这个关系可以看做是带权值的边。一个一维数组保存顶点数据，一个二维数组保存边的权值，这样的二维数组就是邻接矩阵。

这里就简单介绍一个无向的用1来代替之间相邻的示例，权值可以简单看成A点到邻接B点的距离，这里就全部看做相等，1来表示，不相邻就使用0来表示。

具体代码如下：

class MatrixGraph():
    '''
    初始化一个顶点数组与点边二维数组
    n:顶点个数
    '''
 
    def __init__(self, n):
        self.vertexes = []
        self.graph = [[0]*n for j in range(0, n)]
 
    def addVertex(self, n):
        '''
        添加顶点
        return:所有顶点的列表
        '''
        vertexList = self.vertexes
        for i in range(0, n):
            vertex = input("请输入顶点值：").strip()
            if vertex != None and vertex != '#':
                vertexList.append(vertex)
        return vertexList
 
    def adjacencyMatrix(self, vertexList):
        '''
        邻接矩阵，邻边使用1表示
        '''
        while True:
            start = input("请输入起点：").strip()
            end = input("请输入相邻节点：").strip()
            if start == '#' and end == '#':
                break
            if start == end and (start != '#' and end != '#'):
                print("相邻节点不能是自己")
                continue
            if (start not in vertexList) or (end not in vertexList):
                print("图中没有此节点，请重新输入")
                continue
            else:
                i = vertexList.index(start)
                j = vertexList.index(end)
                self.graph[i][j] = 1
                self.graph[j][i] = 1
        return self.graph
 
    def printGraph(self, n):
        graph = self.graph
        for i in range(0, n):
            print(graph[i], end="\n")
 
 
if __name__ == '__main__':
    n = int(input("请输入顶点个数：").strip())
    matrixGraph = MatrixGraph(n)
    vertextList = matrixGraph.addVertex(n)
    print("图中所有顶点：", vertextList)
    matrixGraph.adjacencyMatrix(vertextList)
    matrixGraph.printGraph(n)

'''
请输入顶点个数：5
请输入顶点值：A
请输入顶点值：B
请输入顶点值：C
请输入顶点值：D
请输入顶点值：E
图中所有顶点： ['A', 'B', 'C', 'D', 'E']
请输入起点：A
请输入相邻节点：B
请输入起点：A
请输入相邻节点：C
请输入起点：A
请输入相邻节点：D
请输入起点：A
请输入相邻节点：E
请输入起点：C
请输入相邻节点：D
请输入起点：#
请输入相邻节点：#
[0, 1, 1, 1, 1]
[1, 0, 0, 0, 0]
[1, 0, 0, 1, 0]
[1, 0, 1, 0, 0]
[1, 0, 0, 0, 0]
'''

比如这5个顶点与相邻边组成的一张图（邻接矩阵），最后的二维数组我们来看下：

[0, 1, 1, 1, 1]
[1, 0, 0, 0, 0]
[1, 0, 0, 1, 0]
[1, 0, 1, 0, 0]
[1, 0, 0, 0, 0]

我们可以看到主对角线（左上角到右下角）中间都是0，其余是一种对称结构。初学者可能对这个矩阵不是很了解，怎么看出相邻边，我这里解释下。

A点相邻的有B,C,D,E四个节点，所以第一行的索引位置1234都为1
B点的相邻节点，只有A这个节点是吧，所以就是索引0位置为1
C节点，相邻节点有A和D两个节点，所以在索引0和3的位置为1
D节点的相邻节点是A和C，所以在索引0和2的位置为1
E节点只有A相邻，所以就是索引在0位置的值为1

这里的1就是权值，如果想要表示A点到B点的权值为2，A到C点的权值为3，那么这里就分别赋值为2和3即可，这种叫做加权相邻边的矩阵，挺简单的。