加餐部分 – 潘登同学的图论笔记

加餐第一题： 骑士周游问题DFS实现

• 题目：

考虑国际象棋棋盘上某个位置的一只马，它是否可能只走63步，正好走过除起点外的其他63个位置各一次？如果有一种这样的走法，则称所走的这条路线为一条马的周游路线。试设计一个算法找出这样一条马的周游路线。

此题实际上是一个汉密尔顿通路问题，可以描述为：

在一个8×8的方格棋盘中，按照国际象棋中马的行走规则从棋盘上的某一方格出发，开始在棋盘上周游，如果能不重复地走遍棋盘上的每一个方格，
这样的一条周游路线在数学上被称为国际象棋盘上马的哈密尔顿链。请你设计一个程序，从键盘输入一个起始方格的坐标，由计算机自动寻找并打印
出国际象棋盘上马的哈密尔顿链。

算法很经典不过多解释了，但在实现的过程中用了一个启发式的算法Warnsdorff算法，目的只是加快DFS过程

• 骑士周游问题详解–陈斌老师（北大数据结构）

话不多说，上代码！！！

#%%骑士周游问题
from Vertex import Vertex # 导入Vertex
from Graph import Graph  # 导入之前实现的Graph

class New_Vertex(Vertex):  # 某一个具体问题的数据结构需要继承原有数据结构
    def __init__(self, key):
        super().__init__(key)
        self.color = 'white'  # 新增类属性(用于记录节点是否被走过)

    # 新增类方法, 设置节点颜色
    def setColor(self, color):
        self.color = color

    # 新增类方法, 查看节点颜色
    def getColor(self):
        return self.color

class New_Graph(Graph):  # 继承Graph对象
    def __init__(self):
        super().__init__()

    # 重载方法  因为原先Graph中新增节点用的是Vertex节点,但现在是用New_Vertex
    def addVertex(self, key):   # 增加节点
        '''
        input: Vertex key (str)
        return: Vertex object
        '''
        self.numVertices = self.numVertices + 1
        newVertex = New_Vertex(key)   # 创建新节点
        self.vertList[key] = newVertex
        return newVertex

class Solution(object):
    # 构造图
    def knightGraph(self, bdSize):
        ktGraph = New_Graph()
        for row in range(bdSize):
            for col in range(bdSize):
                index = bdSize * row + col  # 当前节点索引(key)
                newPositions = self.genLegalMoves(row, col, bdSize)  # 下一个节点的集合
                for i in newPositions:
                    index_next = bdSize*i[0]+i[1]
                    ktGraph.addEdge(index, index_next, 1)
        return ktGraph

    # 判断马的走法是否合法
    def genLegalMoves(self, x, y, bdSize):
        newMoves = []
        # 马的走棋规则
        moveOffsets = [(-1, -2), (-1, 2), (-2, -1), (-2, 1),
                       (1, -2), (1, 2), (2, -1), (2, 1)]
        for i in moveOffsets:
            newX = x + i[0]
            newY = y + i[1]
            if self.legalCoord(newX, bdSize) and self.legalCoord(newY, bdSize):
                newMoves.append((newX, newY))
        return newMoves

    def legalCoord(self, x, bdSize):   # 查看落点是否越界
        if x >= 0 and x < bdSize:
            return True
        else:
            return False

    # 深度优先搜索
    def DFS(self, g, start):
        result = []

        # 回溯
        def trace(path, g, start):   # path是探索的路径 g是图，start是起始的节点
            start.setColor('gray')  # 将正在探索的节点设置为灰色
            path.append(start)
            if len(path) == 64:   # 64是总的目标（走完棋盘）
                result.append(list(path))
                return
            else:
                for i in list(start.getConnections()):
                    if i.getColor() == 'white':
                        trace(path, g, i)
                        path.pop()
                        i.setColor('white')

        trace([], g, start)
        return result

    # 回溯改进Warnsdorff算法
    # 将strat 的合法移动目标棋盘格排序为：具有最少合法移动目标的格子优先搜索
    # def Warnsdorff(g, start):

    # Warnsdorff算法
    def Warnsdorff(self, path, g, start):   # path是探索的路径 g是图，start是起始的节点
        start.setColor('gray')  # 将正在探索的节点设置为灰色
        path.append(start)
        temp_choice = list(self.orderByAvail(start))
        for i in temp_choice:
            if i.getColor() == 'white':
                self.Warnsdorff(path, g, i)
                if len(path) == 64:   # 64是总的目标（走完棋盘）(这与完全遍历有区别)
                    return path  # 完全遍历的判断语句就在函数前端，这个只要找到一个就行
                path.pop()
                i.setColor('white')

    # 这个函数的目的是把要探索的节点按照走的先后次序进行排序（按照下下步选择少的排在前面）
    # 相当于先验知识（启发式算法）
    def orderByAvail(self, start):
        reslist = []
        for i in start.getConnections():
            if i.getColor() == 'white':
                c = 0
                for j in i.getConnections():
                    if j.getColor() == 'white':
                        c += 1
                reslist.append((c, i))
        reslist.sort(key=lambda x: x[0])
        return [y[1] for y in reslist]

        # trace1([], g, start)
        # return result


if __name__ == '__main__':
    s = Solution()
    g = s.knightGraph(8)
    path = s.Warnsdorff([], g, g.getVertex(0))
    for i in path:
        print(i.getId(), end=' ')

加餐第二题： 词梯问题BFS实现

• 题目：

从一个单词演变到另一个单词，其中的过程可以经过多个中间单词。 要求是相邻两个单词之间差异只能是1个字母

• 从FOOL到SAGE的过程
  

注意的地方：

图结构的构建有点复杂，主要思想就是构建词梯桶，把两个相差一个字符的单词构建一条边

然后就是BFS的实现了

广度优先算法（先从距离为1开始搜索节点，搜索完所有距离为k才搜索距离为k+1）

(图的数据结构修改)
为了跟踪顶点的加入过程，并避免重复顶点，要为顶点增加三个属性
距离distance:从起始顶点到此顶点路径长度
前驱顶点predecessor:可反向追随到起点
颜色color：标识了此顶点是尚未发现（白色）,已经发现（灰色）,还是已经完成探索（黑色）

(新加队列数据结构)
还需用一个队列Queue来对已发现的顶点进行排列
决定下一个要探索的顶点（队首顶点）

BFS算法过程
从起始顶点s开始，作为刚发现的顶点，标注为灰色，距离为0，前驱为None，
加入队列，接下来是个循环迭代过程：

从队首取出一个顶点作为当前顶点；遍历当前顶点的邻接顶点，如果是尚未发现的白色顶点，则将其颜色改为灰色（已发现），距离增加1，前驱顶点为当前顶点，加入到队列中

遍历完成后，将当前顶点设置为黑色（已探索过），循环回到步骤1的队首取当前顶点

• 词梯问题详解–陈斌老师（北大数据结构）

话不多说，上代码！！！

#%% 词梯问题BFS算法
from Vertex import Vertex # 导入Vertex
from Graph import Graph  # 导入之前实现的Graph
import sys

class New_Vertex(Vertex):  # 某一个具体问题的数据结构需要继承原有数据结构
    def __init__(self, key):
        super().__init__(key)
        self.color = 'white'  # 新增类属性(用于记录节点是否被走过)
        self.dist = sys.maxsize  # 新增类属性(用于记录strat到这个顶点的距离)初始化为无穷大
        self.pred = None  # 顶点的前驱 BFS需要

    # 新增类方法, 设置节点颜色
    def setColor(self, color):
        self.color = color

    # 新增类方法, 查看节点颜色
    def getColor(self):
        return self.color

    # 新增类方法, 设置节点前驱
    def setPred(self, p):
        self.pred = p

    # 新增类方法, 查看节点前驱
    def getPred(self):  # 这个前驱节点主要用于追溯，是记录离起始节点最短路径上
        return self.pred    # 该节点的前一个节点是谁

    # 新增类方法, 设置节点距离
    def setDistance(self, d):
        self.dist = d

    # 新增类方法, 查看节点距离
    def getDistance(self):
        return self.dist

class New_Graph(Graph):  # 继承Graph对象
    def __init__(self):
        super().__init__()

    # 重载方法  因为原先Graph中新增节点用的是Vertex节点,但现在是用New_Vertex
    def addVertex(self, key):   # 增加节点
        '''
        input: Vertex key (str)
        return: Vertex object
        '''
        if key in self.vertList:
            return
        self.numVertices = self.numVertices + 1
        newVertex = New_Vertex(key)   # 创建新节点
        self.vertList[key] = newVertex
        return newVertex

# %词梯问题:采用字典建立桶（每个桶有三个字母是相同的  比如head,lead,read
# 那么每个词梯桶内部所有单词都组成一个无向且边为1的图


def buildGraph(wordfile):
    d = {}
    g = New_Graph()
    wfile = open(wordfile, 'r')
    # 创建桶，每个桶中只有一个字母是不同的
    for line in wfile:
        word = line[:-1]
        for i in range(len(word)):   # 每一个单词都可以属于4个桶
            bucket = word[:i] + '_' + word[i+1:]
            if bucket in d:
                d[bucket].append(word)
            else:
                d[bucket] = [word]
    # 在桶内部建立图
    for bucket in d.keys():
        for word1 in d[bucket]:
            for word2 in d[bucket]:
                if word1 != word2:
                    g.addEdge(word1, word2)
    return g


# %广度优先算法（先从距离为1开始搜索节点，搜索完所有距离为k才搜索距离为k+1）
'''
为了跟踪顶点的加入过程，并避免重复顶点，要为顶点增加三个属性
    距离distance:从起始顶点到此顶点路径长度
    前驱顶点predecessor:可反向追随到起点
    颜色color：标识了此顶点是尚未发现（白色）,已经发现（灰色）,还是已经完成探索（黑色）
还需用一个队列Queue来对已发现的顶点进行排列
    决定下一个要探索的顶点（队首顶点）

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


class Queue:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def enqueue(self, items):   # 往队列加入数据
        self.items.insert(0, items)

    def dequeue(self):
        return self.items.pop()

    def size(self):
        return len(self.items)


def BFS(g, start):   # 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('balck')


def traverse(y):
    x = y
    while (x.getPred()):
        print(x.getId())
        x = x.getPred()
    # print(x.getPred())


if __name__ == '__main__':
    wordgraph = buildGraph('fourletterwords.txt')
    BFS(wordgraph, wordgraph.getVertex('FOOL'))
    traverse(wordgraph.getVertex('SAGE'))
    print('FOOL')

看到结果输出的与上图不一致，但是经过的顶点的数量是相同的，都是最短路径，所以OK！！！

加餐第三题： 强连通分支（kosaraju算法）

关于强连通分支，前面有做过铺垫，找强连通分支有很多算法，这里将一个好理解的算法kosaraju算法，

• 算法流程：

强连通分量分解可以通过两次简单的DFS实现。第一次DFS时，选取任意顶点作为起点，遍历所有尚未访问过的顶点，并在回溯前给顶点标号(post order，后序遍历)。对剩余的未访问过的顶点，不断重复上述过程。

完成标号后，越接近图的尾部(搜索树的叶子)，顶点的标号越小。第二次DFS时，先将所有边反向，然后以标号最大的顶点为起点进行DFS。这样DFS所遍历的顶点集合就构成了一个强连通分量。之后，只要还有尚未访问的顶点，就从中选取标号最大的顶点不断重复上述过程。

附上源视频链接

强连通分支（kosaraju算法）–陈斌老师（北大数据结构）

但是视频中可没有代码喔！！

那pd的nb之处还是展现出来了喔！！

话不多说，上代码！！！

# %%通用的深度优先搜索(kosaraju算法)
import sys


class Vertex:
    def __init__(self, key):
        self.id = key
        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 __str__(self):   # 显示设置
        return str(self.id) + 'connectTo:' + \
               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]

    def setColor(self, color):
        self.color = color

    def getColor(self):
        return self.color

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

    def getPred(self):  # 这个前驱节点主要用于追溯，是记录离起始节点最短路径上
        return self.pred    # 该节点的前一个节点是谁

    def setDistance(self, d):
        self.dist = d

    def getDistance(self):
        return self.dist

    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


class DFSGraph:
    def __init__(self):
        self.vertList = {}  # 这个虽然叫list但是实质上是字典
        self.numVertices = 0
        self.time = 0   # DFS图新增time 用于记录执行步骤

    def addVertex(self, key):   # 增加节点
        self.numVertices = self.numVertices + 1
        newVertex = Vertex(key)   # 创建新节点
        self.vertList[key] = newVertex
        return newVertex

    def getVertex(self, key):   # 通过key获取节点信息
        if key in self.vertList:
            return self.vertList[key]
        else:
            return None

    def __contains__(self, n):  # 判断节点在不在图中
        return n in self.vertList

    def addEdge(self, from_key, to_key, cost=1):    # 新增边
        if from_key not in self.vertList:      # 不再图中的顶点先添加
            self.addVertex(from_key)
        if to_key not in self.vertList:
            self.addVertex(to_key)
        # 调用起始顶点的方法添加邻边
        self.vertList[from_key].addNeighbor(self.vertList[to_key], cost)

    def getVertices(self):   # 获取所有顶点的名称
        return self.vertList.keys()

    def __iter__(self):  # 迭代取出
        return iter(self.vertList.values())

    def dfs(self):
        for v in self:
            v.setColor('white')   # 先将所有节点设为白色
            v.setPred(-1)

        for v in self:
            if v.getColor() == 'white':
                self.dfsvisit(v)  # 如果还有未包括的顶点,则建立森林

    def dfsvisit(self, stratVertex):
        stratVertex.setColor('gray')
        self.time += 1   # 记录步数
        stratVertex.setDiscovery(self.time)

        for v in stratVertex.getConnections():
            if v.getColor() == 'white':
                v.setPred(stratVertex)   # 把下一个节点的前驱节点设为当前节点
                self.dfsvisit(v)  # 递归调用自己
        stratVertex.setColor('black')  # 把当前节点设为黑色
        self.time += 1   # 设为黑色表示往回走了，所以步数加一
        stratVertex.setFinish(self.time)

    def kosaraju(self):  # kosaraju划分强连通分支
        self.dfs()  # 第一步调用DFS，得到节点的Finish_time
        # 第二步将图转置
        self.transposformed()  # 将图转置
        # 对转置的图调用DFS,但不能直接调用
        num = self.numVertices
        max_finish = 0
        while num > 0:
            for v in self:
                # 得到最大的Finish_time
                if v.getColor() == 'black' and v.fin >= max_finish:
                    max_finish = v.fin

            for v in self:
                # 按照Finish_time从大到小组成深度优先森林
                if v.fin == max_finish:
                    self.kosaraju_dfsvisit(v)
                    print('其中一个强联通分支是:')
                    for v in self:
                        if v.getColor() == 'gray':  # 将灰色的都返回
                            print(v.getId(), end=' ')
                            v.setColor('white')  # 将颜色设为白色
                            num -= 1   # 记录还剩多少节点
            max_finish = 0

    def transposformed(self):
        Edge_tuples = []  # 里面装 某节点-指向->相邻节点和相邻边
        for v1 in self:  # 把所有节点取出来
            for v2 in self:  # 两两交换边
                if v2 in v1.getConnections():
                    Edge_tuples.append((v1, v2, v1.getWeight(v2)))
            v1.connectedTo = {}  # 把v1的全部变成空
        for v3 in Edge_tuples:
            current_Vertex = v3[1]  # current_Vertex 是原本被指向的节点
            current_Vertex.addNeighbor(v3[0], v3[2])

    def kosaraju_dfsvisit(self, stratVertex):
        # 写一个专门用于kosaraju逆序的dfs
        stratVertex.setColor('gray')  # 把color从黑色转为灰色
        for v in stratVertex.getConnections():
            if v.getColor() == 'black':
                v.setPred(stratVertex)   # 把下一个节点的前驱节点设为当前节点
                self.kosaraju_dfsvisit(v)  # 递归调用自己


if __name__ == '__main__':
    g = DFSGraph()
    g.addEdge('A', 'B')
    g.addEdge('B', 'E')
    g.addEdge('B', 'C')
    g.addEdge('C', 'F')
    g.addEdge('E', 'A')
    g.addEdge('E', 'D')
    g.addEdge('D', 'G')
    g.addEdge('D', 'B')
    g.addEdge('G', 'E')
    g.addEdge('F', 'H')
    g.addEdge('H', 'I')
    g.addEdge('I', 'F')
    g.kosaraju()

正确结果：如图

可以看到我们的结果与正确结果一致，OK！！！！

加餐第四题： 图的最短路径算法（Dijkstra算法）+ prim最小生成树

对于最短路径我们当然可以用DFS或者BFS来找到，但是Dijkstra算法也是一个很经典的算法

背景介绍在这里

图的最短路径算法–陈斌老师（北大数据结构）

话不多说，上代码！！！

# %%图的最短路径算法（Dijkstra算法）无法处理权值为负的情况

import sys
import numpy as np


class Binheap():
    def __init__(self):
        self.heaplist = [(0, 0)]   # 专门用于Dijkstra算法，第一个是节点第二个是数值
        # 因为要利用完全二叉树的性质，为了方便计算，把第0个位置设成0，不用他
        '''
        完全二叉树的特性  如果某个节点的下标为i
        parent = i//2
        left = 2*i
        right = 2*i +1
        '''
        self.currentSize = 0

    def perUp(self, i):
        while i//2 > 0:
            # 如果子节点比父节点要小，就交换他们的位置
            if self.heaplist[i][1] < self.heaplist[i//2][1]:
                self.heaplist[i], self.heaplist[i//2] =\
                                        self.heaplist[i//2], self.heaplist[i]
            i = i//2

    def insert(self, k):
        self.heaplist.append(k)
        self.currentSize += 1
        self.perUp(self.currentSize)

    def delMin(self):
        # 删掉最小的那个就是删掉了根节点，为了不破坏heaplist
        # 需要把最后一个节点进行下沉，下沉路径的选择，选择子节点中小的那个进行交换
        # 先把最后一个与第一个交换顺序
        self.heaplist[1], self.heaplist[-1] =\
                                    self.heaplist[-1], self.heaplist[1]
        self.currentSize -= 1
        self.perDown(1)
        return self.heaplist.pop()

    def minChild(self, i):
        if i*2+1 > self.currentSize:
            return 2*i
        else:
            if self.heaplist[2*i][1] < self.heaplist[2*i+1][1]:
                return 2*i
            else:
                return 2*i+1

    def perDown(self, i):  # 下沉方法
        while 2*i <= self.currentSize:  # 只有子节点就比较
            min_ind = self.minChild(i)
            if self.heaplist[i][1] > self.heaplist[min_ind][1]:
                # 如果当前节点比子节点中小的要大就交换
                self.heaplist[i], self.heaplist[min_ind] =\
                                self.heaplist[min_ind], self.heaplist[i]
                i = min_ind
            else:
                break  # 如果当前节点是最小的就退出循环

    def findMin(self):
        return self.heaplist[1]

    def isEmpty(self):
        return self.heaplist == [(0, 0)]

    def size(self):
        return self.currentSize

    def buildHeap(self, alist):  # 这个alist里面装的元素是元组
        # 将列表变为二叉堆
        # 采用下沉法 算法复杂度O(N)  如果一个一个插入的话，算法复杂的将会是O(nlgn)
        # 自下而上的下沉（先下沉最底层的父节点）
        i = len(alist)//2
        self.currentSize = len(alist)
        self.heaplist = [(0, 0)] + alist
        while i > 0:
            self.perDown(i)
            i -= 1
        return self.heaplist

    def __iter__(self):
        for item in self.heaplist[1:]:
            yield item

    def __contains__(self, n):    # 判断节点是否在优先队列内（专门为prim写的）
        return n in [v[0] for v in self.heaplist]


class Vertex:
    def __init__(self, key):
        self.id = key
        self.connectedTo = {}
        self.color = 'white'  # 为了解决词梯问题的
        self.dist = sys.maxsize  # 无穷大
        self.pred = None

    def addNeighbor(self, nbr, weight=0):   # 增加相邻边，
        self.connectedTo[nbr] = weight   # 这个nbr是一个节点对象，不是名称

    def __str__(self):   # 显示设置
        return str(self.id) + 'connectTo:' + \
               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]

    def setColor(self, color):
        self.color = color

    def getColor(self):
        return self.color

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

    def getPred(self):  # 这个前驱节点主要用于追溯，是记录离起始节点最短路径上
        return self.pred    # 该节点的前一个节点是谁

    def setDistance(self, d):
        self.dist = d

    def getDistance(self):
        return self.dist


class DIJKSTRAGraph:
    def __init__(self):
        self.vertList = {}  # 这个虽然叫list但是实质上是字典
        self.numVertices = 0

    def addVertex(self, key):   # 增加节点
        self.numVertices = self.numVertices + 1
        newVertex = Vertex(key)   # 创建新节点
        self.vertList[key] = newVertex
        return newVertex

    def getVertex(self, key):   # 通过key获取节点信息
        if key in self.vertList:
            return self.vertList[key]
        else:
            return None

    def __contains__(self, n):  # 判断节点在不在图中
        return n in self.vertList

    def addEdge(self, from_key, to_key, cost=1):    # 新增边
        if from_key not in self.vertList:      # 不再图中的顶点先添加
            self.addVertex(from_key)
        if to_key not in self.vertList:
            self.addVertex(to_key)
        # 调用起始顶点的方法添加邻边
        self.vertList[from_key].addNeighbor(self.vertList[to_key], cost)

    def getVertices(self):   # 获取所有顶点的名称
        return self.vertList.keys()

    def __iter__(self):  # 迭代取出
        return iter(self.vertList.values())

    def Dijkstra(self, startVertex):   # 输入的stratVertex是节点的key
        startVertex = self.vertList[startVertex]
        startVertex.setDistance(0)
        startVertex.setPred(None)   # 将起始节点的前驱节点设置为None
        pq = Binheap()
        pq.buildHeap([(v, v.getDistance()) for v in self])
        while not pq.isEmpty():
            current_tuple = pq.delMin()
            for nextVertex in current_tuple[0].getConnections():
                newDistance = current_tuple[0].getDistance() +\
                                current_tuple[0].getWeight(nextVertex)
                # 如果当下一节点的dist属性大于当前节点加上边权值,就更新权值
                if newDistance < nextVertex.getDistance():
                    nextVertex.setDistance(newDistance)
            # 把更新好的值重新建队
            pq.buildHeap([(v[0], v[0].getDistance()) for v in pq])
            if not pq.isEmpty():
                # 把下一节点的前驱节点设置为当前节点
                nextVertex_set_pred = pq.findMin()[0]
                nextVertex_set_pred.setPred(current_tuple[0])

    def minDistance(self, from_key, to_key):
        self.Dijkstra(from_key)
        to_key = self.getVertex(to_key)
        min_distance = to_key.getDistance()
        while to_key.getPred():
            print(to_key.getId()+'<--', end='')
            to_key = to_key.getPred()
        print(from_key+' 最短距离为:', min_distance)

    def matrix(self, mat):    # 这里的mat用numpy传进来
        key = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
        for i in range(len(mat)):    # 邻接矩阵行表示from_key
            for j in range(len(mat)):  # 列表示to_key
                if i != j and mat[i, j] > 0:
                    self.addEdge(key[i], key[j], mat[i, j])

    def prim(self, startVertex):
        pq = Binheap()
        for v in self:
            v.setDistance(sys.maxsize)
            v.setPred(None)

        startVertex = self.vertList[startVertex]
        startVertex.setDistance(0)
        pq.buildHeap([(v, v.getDistance()) for v in self])
        while not pq.isEmpty():
            current_tuple = pq.delMin()
            for nextVertex in current_tuple[0].getConnections():
                # 注意这里是两顶点找最短边（因为是贪心算法）而不是找全局最短
                newWeight = current_tuple[0].getWeight(nextVertex)
                # 当这个节点在图中且新的权重比旧权重小，就更新权重，更新连接
                if nextVertex in pq and newWeight < nextVertex.getDistance():
                    nextVertex.setDistance(newWeight)
                    nextVertex.setPred(current_tuple[0])
                    # 对优先队列从新排列
                    pq.buildHeap([(v[0], v[0].getDistance()) for v in pq])
        for v in self:
            if v.getPred():
                print(f'节点{v.getId()}的前驱节点是{v.getPred().getId()}')


if __name__ == '__main__':
    DijGraph = DIJKSTRAGraph()
    inf = float('inf')
    a = np.array([[0, 1, 12, inf, inf, inf],
                  [inf, 0, 9, 3, inf, inf],
                  [inf, inf, 0, inf, 5, inf],
                  [inf, inf, 4, 0, 13, 15],
                  [inf, inf, inf, inf, 0, 4],
                  [inf, inf, inf, inf, inf, 0]])
    DijGraph.matrix(a)
    DijGraph.minDistance('A', 'F')
    DijGraph.prim('A')   # 输出最小生成树

写在最后

好啦，我这个阶段的图论笔记就到此为止啦，笔记里面当然有很多写的不好的地方，还有一些算法是没有实现的，比如那个欧拉道路的算法，感兴趣的同学写好了可以PULL到我的Github仓库，

也可以发邮件给我 我的个人邮箱是 395286447@qq.com

然后文章中出现的所有代码都在我的Github仓库里，潘登同学的Github仓库