图

三要素

• 顶点：顶点（也称“节点 node”）是图的基础部分。
• 边：边（也称“弧 arc”）是图的另一个基础组成部分。如果一条边连接两个顶点，则表示两者具有联系。边可以是单向的，也可以是双向的。
• 权重：为了表达从一个顶点到另一个顶点的“代价”，可以给边赋权。

二概念

• 路径：图中的路径，是由边依次连接起来的顶点序列。
• 环：有向图里的环是首尾顶点相同的路径。没有环的图称为“无圈图acyclic graph”，没有环的有向图称为“有向无环图 directed acyclic graph 或 DAG”。

图 抽象数据类型（Abstract Data Type,ADT）相关定义

• Graph()：创建一个空的图
• addVertex(vert)：将一个顶点 Vertex 对象加入图中
• addEdge(fromVert, toVert)：添加一条有向边
• addEdge(fromVert, toVert, weight)：添加一条带权的有向边
• getVertex(vertKey)：查找图中名称为 vertKey 的顶点
• getVertices()：返回图中所有顶点列表

图的两种实现方法

• 邻接表

  
  图的邻接表表示

• 邻接矩阵

  
  图的邻接矩阵表示

图的python实现

• 在 Python 中使用字典将使得邻接表的实现变得很容易。在我们实现图表抽象数据类型时，我们可以创建两个类Graph 和 Vertex。Graph 保存了包含所有顶点的主表，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())

广度优先搜索(BFS)算法

已知一个图 G 和它的一个起始顶点 s，广度优先搜索(BFS)通过搜索图中的边来找到图 G 中所有和 s 有路径相连的顶点。
其显著的特点是在搜索达到距离 k+1 的顶点之前，BFS 会找到全部距离为 k 的顶点。有一个很好的方法去想象广度优先搜索（BFS）的运行原理,那就是建造一棵以 s 为根的树的过程，一次建造树的一层，同时，广度优先搜索(BFS)在增加层次前，会保证将始顶点所有的子顶点都添加在了树中。
为了进一步追踪这一过程，这里的 BFS 算法在搜索过程中，会给每一个顶点染色为白色、灰色或黑色。每一个顶点在被构建时都被初始化为白色，在这之后，白色代表的是尚未被发现的顶点。当一个顶点被第一次发现后，它被染成灰色，当广度优先搜索(BFS)完全探索完一个顶点后，它被染成黑色。
这意味着一旦一个节点染成了黑色，它就没有邻近的白色节点；而另一方面，如果一个顶点被标识为了灰色，这就意味着其附近可能还存在着未探索的顶点等待被探索。

深度优先搜索（DFS）算法。

BFS（广度优先搜索算法）是一次建立搜索树的一层，而 DFS 算法则是尽可能深的搜索树的一枝。

拓扑排序

• 拓扑排序可以将一个有向无环图(DAG)转换为一个只含它所有顶点的线性排列，例如如果一个图G包含一个边界(v,w)，然后我们就可以按顺序将顶点 v 放在顶点 w 之前。
• 拓扑排序是深度优先搜索(DFS)的一个简单却有效的应用。拓扑排序的算法遵从以下法则：
  1. 为所求图问题调用 DFS 函数，调用 DFS 的主要原因是为了计算每一个事件顶点的完成时间。
  2. 按完成时间降序将事件顶点存储在一个列表中。

  3. 将列表作为拓扑排序的结果返回。