图的概念

图可以用G=(V,E)来表述，对于图G,V是顶点的集合，E是边的集合。每个边是一个元组(v,w),v和w属于顶点集合V。

• 路径：由边依次连接起来的顶点序列。将路径定义为P=(w1,w2,…,wn) ，其中1<=i<=n-1.无权路径的长度为边的数量，带权路径的长度为所有边的权重之和。
• 圈：有向图里的圈是首尾顶点相同的路径

ADT Graph的实现

顶点Vertex类：包含了顶点信息，以及顶点连接边的信息

• 每一个Vertex使用一个字典来记录顶点与顶点之间的连接关系和每条连接边的权重，这个字典被称作connectionedTo

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):  #该方法被用来返回以connectionTo字典中的实例变量所表示的邻接表中的所有顶点
        return self.connectedTo.keys()
    
    def getId(self):
        return self.id
    
    def getWeight(self, nbr):  #该方法通过一个参数返回顶点与顶点之间的边的权重
        return self.connectedTo[nbr]

图Graph类：保存了包含所有顶点的主表

• 包含了一个将顶点名称映射到顶点对象的字典，即vertList

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]  #通过key查找顶点
        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.addVertex:
            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())

ADT Grapgh实现代码测试：

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]
        
        
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()))

{0: <__main__.Vertex object at 0x000001F151227F08>, 1: <__main__.Vertex object at 0x000001F150ACA388>, 2: <__main__.Vertex object at 0x000001F151208BC8>, 3: <__main__.Vertex object at 0x000001F151208D08>, 4: <__main__.Vertex object at 0x000001F151208A48>, 5: <__main__.Vertex object at 0x000001F151208748>}
( 0 , 1 )
( 0 , 5 )
( 1 , 2 )
( 2 , 3 )
( 3 , 4 )
( 3 , 5 )
( 4 , 0 )
( 5 , 4 )
( 5 , 2 )

图搜索算法

BFS采用队列来存储待访问节点；DFS则是通过递归调用隐式使用了栈

#使用扩展版的Vertex类
class Vertex:
    def __init__(self,num):
        self.id = num
        self.connectedTo = {}
        self.color = 'white'
        self.dist = sys.maxsize
        self.pred = None
        self.disc = 0
        self.fin = 0
    
    def addNeighbor(self,nbr,weight=0):
        self.connectedTo[nbr] = weight
        
    def setColor(self,color):
        self.color = color
        
    def setDistance(self,d):
        self.dist = d

    def setPred(self,p):
        self.pred = p

    def setDiscovery(self,dtime):
        self.disc = dtime
        
    def setFinish(self,ftime):
        self.fin = ftime
        
    def getFinish(self):
        return self.fin
        
    def getDiscovery(self):
        return self.disc
        
    def getPred(self):
        return self.pred
        
    def getDistance(self):
        return self.dist
        
    def getColor(self):
        return self.color
    
    def getConnections(self):
        return self.connectedTo.keys()
        
    def getWeight(self,nbr):
        return self.connectedTo[nbr]
                
    def __str__(self):
        return str(self.id) + ":color " + self.color + ":disc " + str(self.disc) + ":fin " + str(self.fin) + ":dist " + str(self.dist) + ":pred \n\t[" + str(self.pred)+ "]\n"
    
    def getId(self):
        return self.id

广度优先搜索BFS

广度优先搜索Breadth First Search：最简单算法之一

• 1.给定图G，以及开始搜索的起始顶点s
  • BFS搜索所有从s可到达顶点的边，而且在达到更远的距离k+1的顶点之前，BFS会找到全部距离为k的顶点
  • 可以想象以s为根，构建一棵树的过程，从顶部向下逐步增加层次
  • 广度优先搜索能保证在增加层析之前，添加了所有兄弟节点到树中
  • 跟踪顶点的加入过程，并避免重复顶点
    • 距离distance：从起始顶点到此顶点路径长度
    • 前驱顶点predecessor：可反向追溯到起点
    • 颜色color：标识了此顶点是尚未发现（白色）、已经发现（灰色）、还是已经完成探索（黑色）
  • 排列顶点：用一个队列Queue来对已发现的顶点进行排列
    • 决定下一个要探索的顶点（队首顶点）

• 2.过程：从起始顶点s开始，作为刚发现的顶点，标注为灰色，距离为0，前驱为None，加入队列，接下来是个循环迭代过程
  • 从队首取出一个顶点作为当前顶点
  • 遍历当前顶点的邻接顶点，如果是尚未发现的白色顶点nbr，则将其颜色改为灰色（已发现），距离增加1，前驱节点为当前节点，加入到队列中
  • 遍历完成后，将当前节点设置为黑色（已探索过），循环回到步骤1的队首取当前节点

def bfs(g, start):
    start.setDistance(0)
    start.setPred(None)
    vertQueue = Queue()
    vertQueue.enqueue(start)
    while vertQueue.size() > 0:  #取队首节点作为当前节点
        currentVert = vertQueue.dequeue()
        for nbr in currentVert.getConnections(): #遍历邻接顶点
            if nbr.getColor() == 'white':
                nbr.setColor('gray')
                nbr.setDistance(currentVert.getDistance() + 1)
                nbr.setPred(currentVert)
                vertQueue.enqueue(nbr)
        currentVert.setColor('black')  #当前顶点设为黑色

算法分析：算法主体是两个循环的嵌套

• while循环对每个顶点访问一次：O(|V|)
• 嵌套在while中的for循环，由于每条边只有在其起始顶点u出列的时候才会被检查一次，而每个顶点最多出列一次，所以边最多被检查一次：O(|E|)
• 综合起来，BFS的时间复杂度为：O(|V|+|E|)

深度优先搜索DFS

深度优先搜索Depth First Search：逐层建立搜索树

• 沿着树的单支尽量深入向下搜索
• 如果到无法继续的程度还未找到问题解，就回溯上一层再搜索下一支
• DFS的两个实现算法
  • 一个DFS算法用于解决骑士周游问题，其特点是每个顶点仅访问一次
  • 另一个DFS算法更为通用，允许顶点被重复访问，可作为其他图算法的基础

骑士周游专用算法

骑士周游问题是一种特殊的对图进行深度优先搜索，其目的是建立一个没有分支的最深的深度优先树，表现为一条线性的包含所有节点的退化树

• 关键思路：如果沿着单支深入搜索到无法继续（所有合法移动都已经被走过了）时，路径长度还没有达到预定值（8*8棋盘为63），那么就清除颜色标记，返回到上一层。换一个分支继续深入搜索
• 引用一个栈来记录路径：实施返回上一层的回溯操作

def knightTour(n, path, u, limit): #n：层次；path：路径；u：当前顶点；limit：搜索总深度
    u.setColor('gray')
    path.append(u) #当前顶点加入路径
    
    if n < limit:
        nbrList = list(u.getConnections())  #对所有合法移动逐一深入
        i = 0
        done = False
        while i < len(nbrList) and not done:
            if nbrList[i].getColor() == 'white': #选择白色未经过的顶点深入
                done = knightTour(n+1, path, nbrList[i], limit) #层次加1，递归深入
            i = i + 1
        
        #prepare to backtrack    
        if not done: 
            path.pop() #都无法完成总深度，回溯，试本层下一个顶点
            u.setColor('white')
    else:
        done = True
        
    return done

通用DFS

一般的深度优先搜索目标是在图上进行尽量深的搜索，连接尽可能多的顶点，必要时可以进行分支（创建树）。有时候，深度优先搜索会创建多棵树，称为‘深度优先森林’

• 深度优先搜索要用到顶点的‘前驱’属性，来构建树或森林。另外还要设置‘发现时间’和‘结束时间’属性。
  • 发现时间属性：在第几步访问到这个顶点（设置灰色）
  • 结束时间属性：在第几步完成了此顶点探索（设置黑色）
• 带有DFS算法的图实现为Graph的子类
  • 顶点Vertex增加了成员属性Discovery及Finish
  • 图Graph增加了成员time用于记录算法执行的步骤数目

class DFSGraph(Graph):
    def __init__(self):
        super().__init__()
        self.time = 0
    
    def dfs(self):
        for aVertex in self: #颜色初始化
            aVertex.setColor('white')
            aVertex.setPred(-1)
        for aVertex in self:  #self是DFSGraph类的一个实例
            if aVertex.getColor() == 'white': #如果还有未包括的顶点，则建森林
                self.dfsvisit(aVertex)
                
    def dfsvisit(self, startVertex):
        startVertex.setColor('gray')
        self.time += 1   #算法的步数
        startVertex.setDiscovery(self.time)
        for nextVertex in startVertex.getConnections():
            if nextVertex.getColor() == 'white':
                nextVertex.setPred(startVertex)
                self.dfsvisit(nextVertex)   #深度优先递归访问
        startVertex.setColor('black')
        self.time += 1
        startVertex.setFinish(self.time)

DFS构建的树，其顶点的发现时间和结束时间属性，具有类似括号的性质，即一个顶点的发现时间总小于所有子顶点的发现时间，而结束时间则大于所有子顶点的结束时间。

• 树中一个顶点总是更早被发现，更晚被结束探索
• 通用的深度优先搜索算法分析：运行时间包括了方面
  • dfs函数中有两个循环，每个都是|V|次，所以是：O(|V|)
  • dfsvisit函数中的循环则是对当前顶点所连接的定点进行，而且仅有在顶点为白色的情况下才进行递归调用，所以对每条边来说只会运行一步，所以是：O(|E|)。
• 综合来说，DFS的时间复杂度是：O(|V|+|E|)

图的应用

词梯问题

Word Ladder:从一个单词演变到另一个单词，并且不允许转变成一个不存在的单词，其中的过程可以经过多个中间单词

• 要求：相邻两个单词之间差异只能是一个字母，如FOOL变成SAGE
• FOOL -> POOL -> POLL -> POLE -> PALE -> SALE -> SAGE
• 目标：找到最短的单词交换序列（用图来解决）
  • 将可能的单词之间的演变关系表达为图
    • 将单词作为顶点的标识key；如果两个单词之间仅相差1个字母，就在它们之间设一条边
  • 采用广度优先搜索BFS，来搜索从开始单词到结束单词之间的所有有效路径
  • 选择其中最快到达目标单词的路径

• 构建单词关系图（稀疏图）
  • 该图是无向图，且边没有权重
  • 单词关系图可以通过不同的算法来构建（以4个字母的单词列表为例），首先将所有单词作为顶点加入图中，再设法建立顶点之间的边
  • 最直接算法：对每个顶点（单词）与其他所有单词进行比较，如果相差仅1个字母，则建立一条边。时间复杂度：O(n^2)
  • 改进算法：创建大量的桶，每个桶可以存放若干单词。
    • 桶标记：去掉一个字母，通配符‘ _ ’占空的单词，如 _ OPE、P_PE、PO_E、POP _
    • 所有匹配标记的单词都放到这个桶里，所有单词就位后，再在同一个桶的单词之间建立边即可
    • 桶上的标签在字典中作为key，键值value是标签对应的单词列表

#采用单词建立桶
def buildGraph(wordFile):
    d ={}
    g = Graph()
    wfile = open(wordFile, 'r')
    
    #create buckets of words that differ by one letter
    for line in wfile:
        word = line[:-1]
        for i in range(len(word)):
            bucket = word[:i] + '_' + word[i+1:]
            if bucket in d: #4字母单词可属于4个桶
                d[bucket].append(word)
            else:
                d[bucket] = [word]
                
    #add vertices and edges for words in the same bucket
    for bucket in d.keys():
        for word1 in d[bucket]:
            for word2 in d[bucket]:
                if word1 != word2:  #同一个桶单词之间建立边
                    g.addEdge(word1, word2)
    
    return g

在以FOOL为起始顶点，遍历了所有顶点，并为每个顶点着色、赋距离和前驱之后，既可以通过一个回途追溯函数来确定任何单词顶点到FOOL的最短词梯

def traverse(y):
    x = y
    while(x.getPred()):
        print(x.getId())
        x = x.getPred()
    print(x.getId())
    
wordgraph = buildGraph("fourletterwords.txt")
bfs(wordgraph, wordgraph.getVertex('FOOL'))
traverse(wordgraph.getVertex('SAGE'))

算法分析：

• 建立BFS树之后，回溯顶点到起始顶点的过程，最多为：O(|V|)
• 创建单词关系图也需要时间，最多为：O(|V|^2)

全部代码如下：

def buildGraph(wordFile):
    d = {}
    g = Graph()    
    wfile = open(wordFile,'r')
    # create buckets of words that differ by one letter
    for line in wfile:
        word = line[:-1]
        for i in range(len(word)):
            bucket = word[:i] + '_' + word[i+1:]
            if bucket in d:
                d[bucket].append(word)
            else:
                d[bucket] = [word]
    # add vertices and edges for words in the same bucket
    for bucket in d.keys():
        for word1 in d[bucket]:
            for word2 in d[bucket]:
                if word1 != word2:
                    g.addEdge(word1,word2)
    return g
    

def bfs(g,start):
    start.setDistance(0)
    start.setPred(None)
    vertQueue = Queue()
    vertQueue.enqueue(start)
    while (vertQueue.size() > 0):
    currentVert = vertQueue.dequeue()
    for nbr in currentVert.getConnections():
        if (nbr.getColor() == 'white'):
        nbr.setColor('gray')
        nbr.setDistance(currentVert.getDistance() + 1)
        nbr.setPred(currentVert)
        vertQueue.enqueue(nbr)
    currentVert.setColor('black') 
    
    
def traverse(y):
    x = y
    while (x.getPred()):
        print(x.getId())
        x = x.getPred()
    print(x.getId())


wordgraph = buildGraph("fourletterwords.txt")

bfs(wordgraph, wordgraph.getVertex('FOOL'))

traverse(wordgraph.getVertex('SAGE'))

骑士周游问题

骑士周游：在一个国际象棋棋盘（8*8）上，一个棋子‘马’（骑士），按照马走日的规则，从一个格子出发，要走遍所有棋盘格恰好一次。把一个这样的走棋序列称为一次‘周游’。

• 合格的周游数量有1.305*(10^35)这么多
• 采用图搜索算法的解决方案：
  • 首先将合法走棋次序表示为一个图
  • 采用图搜索算法搜寻一个长度为（行*列-1）的路径，路径上包含每个顶点恰一次。

• 构建骑士周游图
  • 将棋盘格作为顶点
  • 按照‘马走日’规则的走棋步骤作为连接边
  • 建立每一个棋盘格的所有合法走棋步骤能够到达的棋盘格关系图
  • 8*8棋盘生成的图具有336条边，相比全连接的4096条边，仅8.2%，是稀疏图；且靠近边的格子比中心的格子连接的边更少
  • 函数knightGraph遍历整张棋盘，在每个格子上该函数调用genLegalMoves辅助函数来创建当前这个格子上骑士所有合法移动的列表。所有的合法移动都被转换为图上的边。另一个辅助函数posToNodeId根据棋盘上位置的行列信息转换为一个线性定点数

def knightGraph(bdSize):
    ktGraph = Graph()
    for row in range(bdSize): #遍历每个格子
        for col in range(bdSize):
            nodeId = posToNodeId(row, col, bdSize)
            newPisitions = genLegalMoves(row, col, bdSize) #单步合法走棋
            for e in newPisitions:
                nid = posToNodeId(e[0], e[1], bdSize)
                ktGraph.addEdge(nodeId, nid) #添加边及顶点
    return ktGraph

def genLegalMoves(x, y, bdSize):
    newMoves = []
    moveOffsets = [(-1, -2), (-1, 2), (-2, -1), (-2, 1), (1, -2), (1, 2), (2, -1), (2, -2)] #马走日的8个格子
    for i in moveOffsets:
        newX= x + i[0]
        newY = y + i[1]
        if legalCoord(newX, bdSize) and legalCoord(newY, bdSize):
            newMoves.append((newX, newY))
    return newMoves

def legalCoord(x, bdSize):  #确认不会走出棋盘
    if x >= 0 and x < bdSize:
        return True
    else:
        return False
    
def posToNodeId(row, col, bdSize):
    return row * bdSize + col

初始算法

初始算法中nbrList，直接以原始顺序来确定深度优先搜索的分支次序

def knightTour(n, path, u, limit): #n：层次；path：路径；u：当前顶点；limit：搜索总深度
    u.setColor('gray')
    path.append(u) #当前顶点加入路径
    
    if n < limit:
        nbrList = list(u.getConnections())  #对所有合法移动逐一深入
        i = 0
        done = False
        while i < len(nbrList) and not done:
            if nbrList[i].getColor() == 'white': #选择白色未经过的顶点深入
                done = knightTour(n+1, path, nbrList[i], limit) #层次加1，递归深入
            i = i + 1
        
        #prepare to backtrack    
        if not done: 
            path.pop() #都无法完成总深度，回溯，试本层下一个顶点
            u.setColor('white')
    else:
        done = True
        
    return done

• 上述算法的性能高度依赖于棋盘大小，其搜索过程表现为一个层次为n的树
• 时间复杂度为：O(k^n)，其中n是棋盘格数目

Warnsdorff算法

DFS算法是指数时间复杂度算法，可以在实际性能上加以大幅度改进

• 对nbrList的灵巧构造，以特定方式排列顶点访问次序，使搜索时间降低到秒级。
• 仅修改了遍历下一格的次序:将u的合法移动目标棋盘格排序为：具有最少合法移动目标的格子优先搜索
• 采用先验的知识来改进算法性能的做法，称为‘启发式规则heuristic’
  • 启发式规则经常用于人工智能领域
  • 可以有效地减小搜索范围、更快地达到目标等等，能够在最短时间内从海量的棋局落子点搜索树中定位最佳落子。

def orderByAvail(n):
    resList = []
    for v in n.getConnections():
        if v.getColor() == 'white':
            c = 0
            for w in v.getConnections():
                if w.getColor() == 'white':
                    c = c + 1
            resList.append((c, v))
            
    #格式：key=lambda 元素: 元素[字段索引]
    resList.sort(key=lambda x: x[0]) #按照列表中第一个元素排序;lambda 用于匿名函数，可以免去命名函数的麻烦
    return [y[1] for y in resList]

def knightTourBetter(n,path,u,limit):  #use order by available function
        u.setColor('gray')
        path.append(u)
        if n < limit:
            nbrList = orderByAvail(u)
            i = 0
            done = False
            while i < len(nbrList) and not done:
                if nbrList[i].getColor() == 'white':
                    done = knightTour(n+1, path, nbrList[i], limit)
                i = i + 1
            if not done:  # prepare to backtrack
                path.pop()
                u.setColor('white')
        else:
            done = True
        return done

拓扑排序

拓扑排序：将一个有向无圈图（DAG）转换为一个只包含它所有顶点的线性排列。例如，如果有一个图G包含一个边界(v,w)然后我们就可以按顺序将顶点v放在顶点w之前。

• 工作项是顶点，依赖关系是有向边
• 深度优先搜索的一个简单却有用的应用
• 拓扑排序的图算法：从工作流程图得到工作次序排列的算法。
  • 为所求图问题调用DFS函数：计算每一个事件顶点的完成时间
  • 按完成时间降序将时间顶点存储在一个列表中
  • 将列表作为拓扑排序的结果返回

强连通分支

强连通分支：在一张图G中定义一个强连通分支C，作为最大的顶点子集C包含于V，因此对其中每一对顶点，均要使其相互联通。即顶点v,w之间都有路径来回，且(v,w)和(w,v)都是C的路径

• 应用：将一个强连通分支中的所有顶点合并为单个最大的顶点，从而简化图的形式
• 转置(Transposition)图：一个有向图G的转置G^T，定义为将图G的所有边的顶点交换次序，如将(v,w)转换为(w,v)。
  • 图和转置图在强连通分支的数量和划分上是相同的。

• 强连通分支算法SCC：发现图中高度相互关联的顶点（高度聚集节点群）
• Kosaraju算法：
  • 调用DFS算法计算图G中每个顶点的完成时间
  • 计算转置图G^T
  • 调用DFS算法计算转置图，但是对每个顶点的搜索循环中，按顶点完成时间倒序的顺序来搜索
  • 上一步中生成的森林中的每一棵树都是一个强连通分支，输出每一棵树每一个顶点的地址从而识别其分支

最短路径问题

• 带权图最短路径问题：与广度优先搜索BFS算法解决的词梯问题相似
  • 如果所有权重相等，则还原到词梯问题

• Dijkstra算法：解决带权最短路径问题的经典算法
  • 迭代算法，得出从一个确定的顶点到其余所有顶点的最短路径，很接近于广度优先搜索算法BFS的结果
  • 新加成员：在顶点Vertex类中的成员dist用于记录从开始顶点到本顶点的最短带权路径长度（权重之和），算法对图中的每个顶点迭代一次
  • 顶点的访问次序由一个优先队列来控制，队列中决定优先级的是顶点dist的大小，越小，优先级越高
  • 实现：最初，只有开始顶点dist设为0，而其他所有顶点dist设为最大整数sys.maxsize(其实设置成比实际问题中可能出现的任何距离都要大的值即可)，全部加入优先队列。随着队列中每个最小dist顶点率先出队，并计算它与邻接顶点的权重，引起其他顶点dist的减小和修改，引起堆重排。并根据更新后的dist优先级再依次出队。
• 该算法只能处理大于0的权重。如果出现负数权重，则算法会陷入无限循环
• 该算法需要具备整个图的数据，数据量大。

#优先队列类
class PriorityQueue:
    
    def __init__(self):
        self.heapArray = [(0,0)]
        self.currentSize = 0

    def buildHeap(self,alist):
        self.currentSize = len(alist)
        self.heapArray = [(0,0)]
        for i in alist:
            self.heapArray.append(i)
        i = len(alist) // 2            
        while (i > 0):
            self.percDown(i)
            i = i - 1
                        
    def percDown(self,i):
        while (i * 2) <= self.currentSize:
            mc = self.minChild(i)
            if self.heapArray[i][0] > self.heapArray[mc][0]:
                tmp = self.heapArray[i]
                self.heapArray[i] = self.heapArray[mc]
                self.heapArray[mc] = tmp
            i = mc
                
    def minChild(self,i):
        if i*2 > self.currentSize:
            return -1
        else:
            if i*2 + 1 > self.currentSize:
                return i*2
            else:
                if self.heapArray[i*2][0] < self.heapArray[i*2+1][0]:
                    return i*2
                else:
                    return i*2+1

    def percUp(self,i):
        while i // 2 > 0:
            if self.heapArray[i][0] < self.heapArray[i//2][0]:
                tmp = self.heapArray[i//2]
                self.heapArray[i//2] = self.heapArray[i]
                self.heapArray[i] = tmp
            i = i//2
 
    def add(self,k):
        self.heapArray.append(k)
        self.currentSize = self.currentSize + 1
        self.percUp(self.currentSize)

    def delMin(self):
        retval = self.heapArray[1][1]
        self.heapArray[1] = self.heapArray[self.currentSize]
        self.currentSize = self.currentSize - 1
        self.heapArray.pop()
        self.percDown(1)
        return retval
        
    def isEmpty(self):
        if self.currentSize == 0:
            return True
        else:
            return False

    def decreaseKey(self,val,amt):
        # this is a little wierd, but we need to find the heap thing to decrease by looking at its value
        done = False
        i = 1
        myKey = 0
        while not done and i <= self.currentSize:
            if self.heapArray[i][1] == val:
                done = True
                myKey = i
            else:
                i = i + 1
        if myKey > 0:
            self.heapArray[myKey] = (amt,self.heapArray[myKey][1])
            self.percUp(myKey)
            
    def __contains__(self,vtx):
        for pair in self.heapArray:
            if pair[1] == vtx:
                return True
        return False
        

import PriorityQueue, Graph, Vertex

def dijkstra(aGraph, start):
    pq = PriorityQueue()
    start.setDistance(0)
    pq.buildHeap([(v.getDistance(),v) for v in aGraph])  #对所有顶点建堆，形成优先队列
    while not pq.isEmpty():
        currentVert = pq.delMin()  #优先队列出队
        for nextVert in currentVert.getConnections():
            newDist = currentVert.getDistance() + currentVert.getWeight(nextVert)
            if newDist < nextVert.getDistance(): #修改出队顶点所邻接顶点的dist属性，并逐个重排队列
                nextVert.setDistance(newDist)
                nextVert.setPred(currentVert)
                pq.decreaseKey(nextVert, newDist)

算法分析：时间复杂度为：O((|V|+|E|)log|V|)

• 将所有顶点加入优先队列并建堆：O(|V|)
• 每个顶点仅出队1次，每次delMin函数花费O(log|V|),一共就是：O(|V|log|V|)
• 每个边关联到的顶点会做一次decreaseKey操作花费O(log|V|),一共就是：O(|E|log|V|)

最小生成树

信息广播问题一般解法：

• 单播解法：由广播源维护一个收听者的列表，将每条消息向每个收听者发送一次
• 洪水解法：将每条消息都散布出去，所有的路由器都将收到的消息转发到自己相邻的路由器和收听者，很多路由器和收听者会不断重复收到相同的消息，永不停止。
  • 问题：容易造成网络洪水灾难
  • 解决：给每条消息附加一个生命值TTL，初始设置为从消息源到最远的收听者的距离，每个路由器收到一条消息，如果TTL大于0，则将TTL减1，再转发出去；若TTL等于0，则直接抛弃该条消息
• 最小生成树解法：最优解法–依赖于路由器关系图上选取具有最小权重的生成树(minimum weight spanning tree)

• 最小生成树：图G(V,E)的最小生成树T，包含所有顶点V，以及E的无圈子集，并且边权重之和最小。
  • 拥有图中所有顶点和最少数量的边，以保持连通的子图。
• Prim算法
  • 属于贪心算法，即每步都沿着最小权重的边向前搜索
  • 思路：如果T还不是生成树，则反复做：找到一条最小权重的可以安全添加的边，将边添加到树中
    • 可以安全添加的边：定义为一端顶点在树中，另一端不在树中的边，以便保持树的无圈特性

import PriorityQueue, Graph, Vertex
import sys

def prim(G, start):
    pq = PriorityQueue()
    for v in G:
        v.setDistance(sys.maxsize)
        v.setPred(None)
    start.setDistance(0)
    pq.buildHeap([(v.getDistance(),v) for v in G])
    while not pq.isEmpty():
        currentVert = pq.delMin()
        for nextVert in currentVert.getConnections():
            newCost = currentVert.getWeight(nextVert)
            if nextVert in pq and newCost < nextVert.getDistance():
                nextVert.setPred(currentVert)
                nextVert.setDistance(newCost)
                pq.decreaseKey(nextVert, newCost)