图及其算法

1.图的基本概念及相关术语

1. 图Graph的概念

• 图Graph是比树更为一般的结构，也是由节点和边构成
  实际上树是一种具有特殊性质的图

• 图可以用来表示现实世界中很多事物
  道路交通系统、航班线路、互联网连接、或者是 大学中课程的先修次序

• 一旦我们对图相关问题进行了准确的描述就可以采用处理图的标准算法来解决那些看起来非常困难的问题

  • 对于人来说，人脑的识别模式能够轻而易举地判断地图中不同地点的相互关联；
  • 但如果用图来表示地图，就可以解决很多地图专家才能解决的问题，甚至远远超越；
  • 互联网是由成千上万的计算机所连接起来的复杂网络，也可以通过图算法来确定计算机之间达成通讯的最短、最快或者最有效的路径

2. 图的术语

• 顶点Vertex（也称“节点Node” ）
  是图的基本组成部分，顶点具有名称标识Key，也可以携带数据项“有效载荷”payload
• 边Edge（也称“弧Arc” ）
  作为2个顶点之间关系的表示，边连接两个顶点；边可以是无向或者有向的，相应的图称作“ 无向图” 和“ 有向图”
• 权重Weight
  为了表达从一个顶点到另一个顶点的“ 成 本 ” ，可以给边赋权；例如公交网络中两个站点之间的 “ 距离” 、 “ 通行时间” 和“ 票价”都可以作为权重。

3. 图的定义

• 一个图G可以定义为G=(V, E)
  • 其中V是顶点的集合， E是边的集合， E中的每条 边e=(v, w)， v和w都是V中的顶点；
  • 如果是带权图，则可以在e中添加权重分量
  • 子图： V和E的子集
• 带权有向图的例子： 6个顶点及9条边
  • 带权有向图，权重为整数
  • 

4. 路径Path

• 图中的路径，是由边依次连接起来的顶点序列；
• 无权路径的长度为边的数量；带权路径的长度为所有边权重的和；
• 如下图的一条路径(v3,v4,v0,v1)
  • 其边为{(v3,v4,7),(v4,v0,1),(v0,v1,5)}
  • 

5. 环Cycle

• 环是首尾顶点相同的路径，如下图中(v5,v2,v3,v5)是一个圈
• 没有环的图称为无环图
• 如果有向图中不存在任何环，则称作“ 有向无环图directed acyclicgraph: DAG”
• 

2.图抽象数据类型及Python实现

1. 抽象数据类型：ADT Graph

• Graph()：创建一个空的图；
• addVertex(vert)：将顶点vert加入图中
• addEdge(fromVert, toVert)：添加有向边
• addEdge(fromVert, toVert, weight)：添加带权的有向边
• getVertex(vKey)：搜索名称为vKey的顶点
• getVertices()：返回图中所有顶点列表
• in：按照vertex in graph的语句形式，返回顶* 点 是否存在图中True/False

2. ADT Graph的实现方法有两种主要形式：

• 邻接矩阵adjacency matrix
• 邻接表adjacency list
• 两种方法各有优劣，需要在不同应用中加以选择

3. 邻接矩阵Adjacency Matrix

• 矩阵的每行和每列都代表图中的顶点
• 如果两个顶点之间有边相连，设定行列值
  • 无权边则将矩阵分量标注为1，或者0
  • 带权边则将权重保存为矩阵分量值
• 邻接矩阵实现法的优点是简单
  • 可以很容易得到顶点是如何相连
• 但如果图中的边数很少则效率低下
  • 成为“ 稀疏sparse” 矩阵
  • 而大多数问题所对应的图都是稀疏的
  • 边远远少于|V|^2这个量级
    

4. 邻接表Adjacency List

• 邻接表adjacency list可以成为稀疏图 的更高效实现方案
  • 维护一个包含所有顶点的主列表（master list）
  • 主列表中的每个顶点，再关联一个与自身有边连接的所有顶点的列表
• 邻接表法的存储空间紧凑高效
  • 很容易获得顶点所连接的所有顶点，以及连接边的信息
  • 

5. 图抽象数据类型的Python实现

# 顶点Vertex类
# Vertex包含了顶点信息，以及顶点连接边
class Vertex:
    def __init__(self, key):
        self.id = key
        self.connectedTo = {}
    def addNeighbor(self , nbr, weight=0):
        self.connectedTo[nbr] = weight
    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]
# Graph保存了包含所有顶点的主表
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
    def __contains__(self,n):
        return n in self.vertList

    def addEdge(self,f,t,cost=0):
        if f not in self.vertList:
            nv = self.addVertex(f) # 不存在的顶点先添加
        if t not in self.vertList:
            nv = self.addVertex(t)
        self.vertList[f].addNeighbor(self.vertList[t], cost)
    def getVertices(self):
        return self.vertList.keys()
    def __iter__(self):
        return iter(self.vertList.values())



g = Graph()
for i in range(6):
    g.addVertex(i)
print(g.vertList)

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(3,5,3)
g.addEdge(4,0,1)
g.addEdge(5,4,8)
g.addEdge(5,2,1)
for v in g:
    for w in v.getConnections():
        print("(%s,%s)" % (v.getId(), w.getId()))