图论-Python

The Art of Graph

图论术语

图表示法

邻接矩阵表示

import sys
#Vertex
class Vertex:
    def __init__(self,node):
        self.id = node
        self.visited = False
    #使用 __init__() 函数将值赋给对象属性
    #或者在创建对象时需要执行的其他操作
    def getVertexID(self):
        return self.id
    def setVertexID(self,id):
        self.id = id
    def setVertexVisited(self):
        self.visited = True
    def addNeighbor(self,neighbor,G):
        G.addEdge(self.id,neighbor)
    def getConnections(self,G):
        return G.adjMatrix[self.id]
    def _str_(self):
        print(str(self.id))
        return str(self.id)
        #str(object, encoding=encoding, errors=errors)
        #object:要转换为字符串的对象
        #encoding:对象的编码,默认是 UTF-8
        #errors:规定解码失败时该怎么办

#Graph
class Graph:
    def __init__(self,numVertices,directed=False): 
        #邻接矩阵
        self.adjMatrix = [[[None] * numVertices] for _ in range(numVertices)]
        #self.adjMatrix = [[0 for i in range(numVertices)] for i in range(numVertices)]
        #顶点数量
        self.numVertices = numVertices
        #顶点(数组vertices[]存储
        self.vertices = []
        #是否可达
        self.directed = directed
        for i in range(0,numVertices):
            newVertex = Vertex(i)
            self.vertices.append(newVertex)

    def addVertex(self,vtx,id):
        if(0<=vtx<self.numVertices):
            self.vertices[vtx].setVertexID(id)

    def getVertex(self,n):
        for vertex in range(0,self.numVertices):
            if n == self.vertices[vertex].getVertexID():
                return vertex
        return None  
  
    def addEdge(self,frm,to,cost=0):
        if self.getVertex(frm)is not None and self.getVertex(to)is not None:
            self.adjMatrix[self.getVertex(frm)][self.getVertex(to)] = cost
  
    def getVertices(self):
        vertices = []
        for vtx in range(0,self.numVertices):
            vertices.append(self.vertices[vtx].getVertexID())
        return vertices  

    def printMatrix(self):
        for u in range(0,self.numVertices):
            row = []
            for v in range(0,self.numVertices):
                if self.adjMatrix[u][v] is not None: 
                    row.append(str(self.adjMatrix[u][v]))
                else : '/'
            print(row)

    def getEdges(self):
        edges = []
        for u in range(0,self.numVertices):
            for v in range(0,self.numVertices):
                if self.adjMatrix[u][v] is not None :
                    #横坐标
                    vID = self.vertices[u].getVertexID()
                    #纵坐标
                    wID = self.vertices[v].getVertexID()
                    edges.append((vID,wID,self.adjMatrix[u][v])) 
        return edges

    def getNeighbors(self,n):
        neighbors = []
        for vtx in range(0,self.numVertices):
            if n == self.vertices[vtx].getVertexID():
                for neighbor in range(0,self.numVertices):
                    if(self.adjMatrix[vtx][neighbor]is not None):
                        neighbors.append(self.vertices[neighbor].getVertexID())
        return neighbors

偶遇NetworkX之后，发现轮子白造了

函数无法显示图片，解决：

import matplotlib.pyplot as plt
draw(G)
plt.show()

networkx教程