图抽象数据类型的特点及python实现

图抽象数据类型：ADT Graph

ADT Graph 的实现方法：
（1）邻接矩阵
矩阵的每行和每列都代表图中的顶点，若两各顶点之间有边连接，设定行列值或权重。无权边则将分量标注为1。
优点：简单，直观，但边数很少时效率低下。

（2）邻接列表
维护一个包含所有顶点的主列表，主列表中每个顶点，再关联一个与自身有边连接的所有顶点的列表，
优点：存储紧凑、高效，很容易获得所有顶点及其连接边的信息。

两种方法有其优劣势，需在不同应用中加以选择。

ADT Graph 实现

## 定义顶点vertex类，包含顶点和连接边信息
class Vertex:
    def __init__(self, key):
        self.id = key
        self.connectedTo = {}

    def addNeighbor(self, nbr, weight=0):
        self.connectedTo[nbr] = weight  # nbr是顶点对象的key

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

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

    def getId(self):
        return self.id

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

##定义了图类，保存了包含所有顶点的主表
class Graph:
    def __init__(self):
        self.verList = {}
        self.numVertices = 0

    def addVertex(self, key):  # 新加顶点
        self.numVertices = self.numVertices + 1
        newVertex = Vertex(key)
        self.verList[key] = newVertex
        return newVertex

    def getVertex(self, n):  # 通过key查找顶点
        if n in self.verList:
            return self.verList[n]
        else:
            return None

    def __contains__(self, n):
        return n in self.verList

    def addEdge(self, f, t, cost=0):
        if f not in self.verList:
            nv = self.addVertex(f)  # 不存在的顶点先添加
        if t not in self.verList:
            nv = self.addVertex(t)
        self.verList[f].addNeighbor(self.verList[t], cost) # 调用起始顶点的方法添加临街边

    def getVertices(self):
        return self.verList.keys()

    def __iter__(self):
        return iter(self.verList.values())
##测试实例：
g=Graph()

for i in range(60):
    g.addVertex(i)
g.addEdge(0,1,5)
g.addEdge(0,5,2)
g.addEdge(1,2,4)
g.addEdge(2,3,9)
g.addEdge(3,4,7)
g.addEdge(4,0,1)
g.addEdge(5,4,8)
g.addEdge(5,2,1)
for v in g:
    for w in v.getConnects():
        print % (v.getId(),w.getId())