322 图的实现1 #

1. 定义顶点类
2. 定义图类
3. 图的顶点相关功能

定义顶点类 #

创建两个类Graph和Vertex。顶点类Vertex的每个顶点通过字典connectTo来跟踪它连接的顶点和每个边的权重，顶点类的定义如下：

class Vertex:
    # 包含5个基本操作，添加某个顶点连接，获取所有连接，获取顶点自身，获取某边权重，打印所有信息
    def __init__(self, key):
        self.id = key
        self.connectedTo = {}

    def addNeighbor(self, nbr, weight=0):
        self.connectedTo[nbr] = weight

    def getConnections(self):
        return self.connectedTo.keys()

    def getId(self):
        return self.id

    def getWeight(self, nbr):
        return self.connectedTo[nbr]

    def __str__(self):
        return str(self.id) + ' connectedTo: ' + str([x.id for x in self.connectedTo])

定义图类 #

一个图是顶点和边的集合，边由顶点的连接关系定义，所以图类最基本含义顶点的集合，另一个值表示顶点的数目

class Graph:
    def __init__(self):
        self.vertList = {}
        self.numVertices = 0

图的顶点相关功能 #

class Graph:
    def __init__(self):
        self.vertList = {}
        self.numVertices = 0

    def addVertex(self, key):
        self.numVertices = self.numVertices + 1
        newVertex = Vertex(key)
        self.vertList[key] = newVertex
        return newVertex

    def getVertex(self, n):
        if n in self.vertList:
            return self.vertList[n]
        else:
            return None

小结 #

习题 #

1. 详细描述一下顶点类个方法的作用
2. 图为什么采用邻接表实现而不是邻接矩阵？