Python图算法之深度优先搜索

原文链接：https://blog.csdn.net/qq_38882327/article/details/89278372

深度优先搜索(Depth First Search, DFS)：
是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。
广度优先搜索算法(BFS)是一次建立搜索树的一层，而DFS算法则是尽可能深的搜索树的一枝。

深度优先森林：
当深度优先搜索算法建立一组树时，称之为深度优先森林。

拓扑排序：
将一个有向无圈图(DAG)转换为一个包含该图所有不重复顶点且路径不可逆的线性排列，称为“拓扑排序”，可以起到指示事件优先级的作用。

拓扑排序是深度优先搜索(DFS)的一个简单却有效的应用。

拓扑排序要满足以下两个条件：
1、每个顶点出现且只出现一次。
2、若A在序列中排在B的前面，则在图中不存在从B到A的路径。

             ┌连通：又称强连通，只有一个极大连通子图(又称强连通分量)，为其本身。
    ┌有向图——|         
    |        └不连通：包含多个极大连通子图。
    |
图——|               ┌只有一个极大连通子图(又称连通分量)，为其本身。
    |       ┌连通——|
    |       |      └极小连通子图为其生成树。
    └无向图——|
            |        ┌多个极大连通子图。
            └不连通——|
                     └多个极小连通子图。

注意：
有向图没有极小连通子图的概念；无向连通图的极小连通子图为无向连通图的生成树。

强连通图：
指每个顶点皆可以经由该图上的边抵达其他每个点的有向图。即对于此图上每个点对(Va, Vb)，皆存在路径Va→Vb以及Vb→Va。

强连通分量(Strongly connected component)：
指一张有向图G的极大强连通子图G’。如果将每个强连通分量缩成一个点，则原图G将会变成一张有向无环图。有向环是一个强连通分量，而任何强连通分量皆具有至少一个有向环。强连通图只有一个强连通分量，即是其自身；非强连通的有向图有多个强连通分量。

连通分量：
无向图G的一个极大连通子图（即连通分量是图G中不被其他连通子图包含的连通子图，所以图G可以有多个连通分量）称为原图G的一个连通分量（或连通分支）。连通图只有一个连通分量，即其自身；非连通的无向图有多个连通分量。

Kosaraju、Tarjan、Gabow算法皆为寻找有向图强连通分量的有效算法。但是由于在Tarjan和Gabow算法的过程中，只需要进行一次深度优先搜索，因而相对Kosaraju算法较有效率，不过Kosaraju算法的优势是依次求出的强连通分量已经是拓扑排序的。

特殊深度优先搜索：
示例：
骑士周游是以创建深度最深并无分支的优先搜索树为目标。

骑士周游问题：
在国际象棋棋盘上仅用“骑士(马)”这个棋子进行操作，目的是找到一条可以让骑士访问所有格子，并且每个格子只能走一次的走棋序列。一个这样的走棋序列称为一次“周游”。

Warnsdorff规则：
指在所有可走且尚未经过的方格中，马只可能走这样一个方格：从该方格出发，马能跳的方格数最少；如果可跳的方格数相等，则从当前位置看，方格序号小的优先。依照这一规则往往可以找到一条路径，但是并不一定能够成功。

走棋规则：
如下图，骑士起始在36位置，在国际象棋中，骑士走棋(类似中国象棋中的马走日)只能从36跳到19、21、30、46、53、51、42、26。

骑士周游棋盘：

在这里插入图片描述

from pythonds.graphs import Graph

# 建立一个 n*n 棋盘对应的完整骑士周游图
def knightGraph(bdSize):
    ktGraph = Graph()                                       #实例化图类
    for row in range(bdSize):                               
        for col in range(bdSize):                           #遍历每个格
            nodeId = posToNodeId(row, col, bdSize)          #遍历生成每个节点的ID值
            # 以下3行可删除，若想显示棋盘，不可删除，若要周游，则需删除，因此处节点ID为str
            # if nodeId < 10:                                   
            #   nodeId = '0' + str(nodeId)
            # print('  ' + str(nodeId), end = '')
            # 以上3行可删除，若想显示棋盘，不可删除，若要周游，则需删除，因此处节点ID为str
            newPositions = genLegalMoves(row, col, bdSize)  #单步合法走棋
            for e in newPositions:                          #遍历每个可走棋位置
                nid = posToNodeId(e[0], e[1], bdSize)       #遍历生成当前格子可走棋位置的ID值
                # 以下3行可删除，若只想显示棋盘，也可删除，若要周游，则需删除，因此处节点ID为str
                # if nid < 10:                                  
                #   nid = '0' + str(nid)
                # print('  ' + str(nid), end = '')
                # 以上3行可删除，若只想显示棋盘，也可删除，若要周游，则需删除，因此处节点ID为str
                ktGraph.addEdge(nodeId, nid)                #添加边及顶点
        #   print('\n')                                     #打印美观，与可走棋位置对应，可删除
        # print('\n')                                       #打印美观，与生成节点ID值对应，可删除
    return ktGraph

# 根据棋盘上位置的行列信息转换成一个线性顶点数
def posToNodeId(row, col, bdSize):
    return (row * bdSize) + col             #生成节点的ID值，8*8的棋盘就是0-63

# 获取骑士当前位置并生成所有八个走棋步骤
def genLegalMoves(row, col, bdSize):
    newMoves = []                           #马在每个格子可走棋位置的集合
    # 马走日，8个格子的偏移量
    moveOffsets = [(-1, -2), (-1, 2), (-2, -1), (-2, 1), (1, -2), (1, 2), (2, -1), (2, 1)]
    for i in moveOffsets:                                   #循环生成以每个格子为起点的8个可走格子
        newR = row + i[0]                   #新的行偏移KzDiJM5d
        newC = col + i[1]                   #新的列偏移
        # 确保不会走出棋盘
        if legalCoord(newR, bdSize) and legalCoord(newC, bdSize):
            newMoves.append((newR, newC))   #将在棋盘内的坐标添加到newMoves中
    return newMoves

# 确保任何个步骤不会超出棋盘(会导致IndexError)
def legalCoord(x, bdSize):
    if x >= 0 and x < bdSize:
        return True
    else:
        return False

# 实现骑士周游：
# 四个参数：n，当前树的深度；path，所搜索过的节点列表；u，当前节点；limit，能搜索的总深度。
def knightTour(n, path, u, limit):
        u.setColor('gray')                  #节点设为灰色，开始周游，初始为白色
        path.append(u)                      #当前节点加入路径
        if n < limit:                       #若搜索深度<搜索总深度，则
            # nbrList = list(u.getConnections())#对所有合法移动逐一深入
            # 将u的邻居按u的邻居的邻居个数的升序排序，即优先搜索邻居少的，这可大幅提升性能
            nbrList = orderByAvail(u)       #获取u的所有邻居，用Warnsdorff提速
            i = 0                           #邻居列表初始索引为0
            done = False                    #初始化为未找到周游路径
            # 当done=False且邻居未找完时，依次循环u的每个邻居
            while i < len(nbrList) and not done:            
                if nbrList[i].getColor() == 'white':        #若邻居为白色，则邻居未探查，深入探查
                    done = knightTour(n + 1, path, nbrList[i], limit)   #深度+1，path增加
                i = i + 1                                   #探查下一个邻居
            if done == False:               #若当前节点的所有子节点(邻居)都已搜索，但仍未找到，则
                path.pop()                  #删除当前节点u，搜索同一父节点(同一层级)的其他兄弟节点
                u.setColor('white')         #当前节点重新设为白色未探查状态
        else:                               #若到达搜索总深度，说明全部格子都走了一遍，则
            done = True                     #已找到周游路径
            for i in path:                  #循环打印路径ID值
                print(i.getId(), end=', ')
        return done

骑士周游算法改进：
这个改进算法被特别以发明者名字命名：Warnsdorff算法。采用先验知识(指无需经验或先于经验获得的知识)改进算法性能的做法，称作“启发式规则heuristic”。

启发式规则经常用于人工智能领域；可以有效地减小搜索范围、更快达到目标等等。

例如棋类程序算法，会预先存入棋谱、布阵口诀、高手习惯等“启发式规则”，能够在最短时间内从海量的棋局落子点搜索树中定位最佳落子。

# 此函数使用Warnsdorff规则(启发式规则)，可以提速骑士周游问题的算法。
def orderByAvail(n):
    resList = []                            #初始化列表
    for v in n.getConnections():            #循环当前节点的所有邻居v
        if v.getColor() == 'white':         #若邻居v节点的颜色为白色，即未探查，则
            c = 0                           #初始化邻居v节点的邻居c的个数
            for w in v.getConnections():    #循环当前节点邻居v的所有邻居c
                if w.getColor() == 'white': #若邻居v的邻居c节点的颜色为白色，即未探查，则
                    c = c + 1               #邻居v的邻居c数量+1
            resList.append((c,v))           #将邻居v的邻居c个数及邻居v组成元组添加到list中
    resList.sort(key=lambda x: x[0])        #将resList按每个元组第一个值的升序排序
    return [y[1] for y in resList]          #返回resList中的节点，即当前节点的所有邻居

g = knightGraph(8)                          #构建完整骑士周游图及每格可走棋位置
u = g.getVertex(53)                         #根据骑士初始节点位置ID值53，获取节点
knightTour(1, [], u, 64)                    #获取骑士周游完整路径

结果为：

53, 63, 46, 31, 14, 4, 10, 0, 17, 2, 8, 25, 40, 57, 51, 61, 55, 38, 23, 6, 12, 29, 39, 54, 60, 50, 56, 41, 24, 9, 3, 13, 7, 22, 5, 15, 21, 11, 1, 16, 26, 32, 49, 59, 44, 34, 19, 36, 30, 20, 35, 18, 28, 45, 62, 47, 37, 27, 33, 43, 58, 48, 42, 52,

通用深度优先搜索：
它的目标是尽可能深地搜索，连接图中尽可能多的顶点以及仅在必要时建立分支。
深度优先搜索会使用两个附加的Vertex类的实例变量。这两个实例变量是“发现时间”和“结束时间”。“发现时间”记录某个顶点第一次出现前算法的操作步数。“完成时间”则是某个顶点被标记为黑色之前算法的操作步数。

示例：

# 深度优先搜索图类，继承了Graph类，节点为白色说明节点尚未被访问，灰色说明节点本身已被访问，黑色说明节点本身及其子树均已被访问
class DFSGraph(Graph):
    def __init__(self):
        #super()可调用父类中的__init__()方法，这样既不会覆盖父类中的同名方法，又能同时实现父类同名方法的功能
        super().__init__()                      
        self.time = 0                           #初始化操作时间

    # 深度优先搜索
    def dfs(self):
        for aVertex in self:                    #self是DFSGraph类的一个实例，遍历实例中的所有节点
            aVertex.setColor('white')           #将所有节点都设为白色
            aVertex.setPred(-1)                 #将所有节点的前导(父节点)都设为-1
        for aVertex in self:                    #重新遍历实例中的所有节点，
            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)        #给当前节点设置完成时间
        #print(startVertex)结果为A:color black:disc 1:fin 12:dist 9223372036854775807:pred [-1](A:黑色:发现时间1:完成时间12:距离源点距离?9223372036854775807:前导-1)之类的数据
        print(startVertex.getId())              #打印节点id值        

# 创建字母图
def letterGraph():
    zmGraph = DFSGraph()
    buzou = ['A', 'B', 'C', 'D', 'E', 'F']
    for i in buzou:
        zmGraph.addVertex(i)                    #添加节点
    zmGraph.addEdge('A', 'B')                   #添加A——>B的边
    zmGraph.addEdge('A', 'D')
    zmGraph.addEdge('B', 'C')
    zmGraph.addEdge('B', 'D')
    zmGraph.addEdge('D', 'E')
    zmGraph.addEdge('E', 'B')
    zmGraph.addEdge('E', 'F')
    zmGraph.addEdge('F', 'C')
    return zmGraph

zmt = letterGraph()                             #创建字母图
zmt.dfs()                                       #深度搜索

结果为：

C
F
E
D
B
A

示例：

# 拓扑排序——摊煎饼
def topoSort():
    topo = DFSGraph()
    buzou = ['eat', 'milk', 'egg', 'oil', 'mix', 'griddle', 'bubbly', 'syrup']
    for i in buzou:
        topo.addVertex(i)                       #添加节点
    topo.addEdge('egg', 'mix')                  #添加egg——>mix的边
    topo.addEdge('oil', 'mix')
    topo.addEdge('milk', 'mix')
    topo.addEdge('mix', 'griddle')
    topo.addEdge('griddle', 'bubbly')
    topo.addEdge('syrup', 'eat')
    topo.addEdge('bubbly', 'eat')
    return topo

topos = topoSort()                              #创建图
topos.dfs()                                     #拓扑排序

结果为：

eat
bubbly
griddle
mix
milk
egg
oil
syrup

示例：

# 拓扑排序，入度即被指向的次数
def toposort(graph):
    in_degrees = dict((u, 0) for u in graph)    #初始化所有顶点入度为0
    # print(in_degrees)
    vertex_num = len(in_degrees)                #获取顶点个数
    for u in graph:                             #循环所有顶点a、b、c、d、e
        for v in graph[u]:                      #循环所有当前顶点的邻居
            in_degrees[v] += 1                  #计算每个顶点的入度
    # print(in_degrees)
    Q = [u for u in in_degrees if in_degrees[u] == 0]   #筛选入度为0的顶点
    Seq = []                                    #初始化最终排序
    while Q:                                    #当存在入度为0的顶点，则循环
        u = Q.pop()                             #默认从最后一个删除
        Seq.append(u)                           #添加一个入度为0的顶点
        for v in graph[u]:                      #循环所有当前顶点的邻居
            in_degrees[v] -= 1                  #该邻居的入度-1
            if in_degrees[v] == 0:              #若该邻居顶点的入度为0，则
                Q.append(v)                     #将其添加到Q中继续循环
    if len(Seq) == vertex_num:  
        return Seq
    else:                   #若循环结束后存在非0入度的顶点说明图中有环，不能拓扑排序
        print("有个环")

# G = {
#   'a':'bce',
#   'b':'d',
#   'c':'bd',
#   'd':'',
#   'e':'cd'
# }
G = {
    'e':'f',
    'o':'f',
    'm':'f',
    'f':'g',
    'g':'b',
    's':'c',
    'b':'c',
    'c':''
}
print(toposort(G))

结果为：

['s', 'm', 'o', 'e', 'f', 'g', 'b', 'c']

Kosaraju算法：
1、 利用深度优先搜索遍历原图，并按出栈的先后顺序把点放进一个线性表里。这里可以每次取任意一个点出发DFS，如果还有点未被DFS到，那么继续任选未被遍历到的点出发DFS。
2、 将整个图转置，Kosaraju算法的核心操作是将所有节点间的路径都翻转过来。
3、 按照线性表中的出栈顺序，从后往前依次作为起点DFS。每次DFS到的就是一个强连通分量。

# 邻接表表示的有向图
N={
    "a":{"b"},   
    "b":{"c"},   
    "c":{"a", "d", "g"},   
    "d":{"e"},   
    "e":{"f"},   
    "f":{"d"},   
    "g":{"h"},   
    "h":{"i"},   
    "i":{"g"}   
}

# 实现翻转图
def re_tr(G):
    GT = {}                                     #初始化反转图
    for u in G:                                 #循环输出原邻接表的键
        for v in G[u]:                          #循环输出原邻接表的值
            if v in GT:                         #若反转图的键中已有该值，则
                GT[v].add(u)                    #将原图对应的键添加给反图对应的键为值
            else:                               #若反转图的键中没有该值，则
                GT[v] = set()                   #初始化反图中v键对应的值
                GT[v].add(u)                    #将原图对应的键添加给反图对应的键为值
    return GT

# 递归实现深度优先排序，G为图，s为起始节点，S为已经排序过的节点
def rec_dfs(G, s, S=None):
    if S is None:                               #若已排序表为空，则
        S = list()                              #初始化已排序列表
    S.append(s)                                 #将该节点添加到已排序表中，标记为已排序
    for u in G[s]:                              #遍历原图中已排序过的节点的值
        if not u in S:                          #若该值尚未被排序，则
            rec_dfs(G, u, S)                    #递归排序
    return S

# 遍历有向图的强连通分量
def walk(G, start, S):                          #参数S避免了通过连通图之间的路径进行遍历
    P, Q = dict(), set()                    #P为强连通分量，存放遍历顺序，Q存放已经遍历过的节点  
    P[start] = None                             #初始化
    Q.add(start)                                #将节点添加到已遍历集合
    # print(P, S)
    while Q:                                    #当已遍历集合不为空时，则循环
        u = Q.pop()                             #选择下一个遍历节点（随机性）
        cha = G[u].difference(P, S)             #返回集合的差集，结果包含在G[u]中，但不在P和S中
        for v in cha:                           #遍历差集
            Q.add(v)                            #依次添加到已遍历集合
            P[v] = u                            #将该节点u添加到强连通分量的对应键
    # print(P)  
    return P

# 获得各个强连通图
def scc(G):
    GT = re_tr(G)                               #将图路径反转
    sccs, seen = [], set()                      #初始化强连通图和过滤集合
    dfs = rec_dfs(G, "a")                       #在原图中以a为起点进行深度优先排序
    for u in dfs:                               #依次遍历原图排序后的节点
        if u in seen:continue                   #若节点在过滤集合中，则跳过当前循环，进入下一循环
        C = walk(GT, u, seen)                   #获取强连通图
        seen.update(C)                          #将获取的强连通图节点添加到过滤集合中
        sccs.append(C)                          #添加到强连通图列表
    return sccs

# 单元测试
print(scc(N))

结果为：

[{'a': None, 'c': 'a', 'b': 'c'}, {'d': None, 'f': 'd', 'e': 'f'}, {'g': None, 'i': 'g', 'h': 'i'}]

Tarjan算法：
是基于递归实现的深度优先搜索，在搜索过程中将顶点不断压入堆栈中，并在回溯时判断堆栈中顶点是否在同一联通分支。函数借助两个辅助数组pre和low，其中pre[u]为顶点u的搜索次序编号，low[u]为顶点u能回溯到的最早的祖先的次序编号。当pre[u]==low[u]时，则弹出栈中顶点并构成一个连通分支。

#求任意顶点开始的联通图，有且仅存在一个，且pre[u] == low[u]
from collections import OrderedDict         #有序字典模块

# 自定义栈类
class Stack(object):
    def __init__(self):
        self.items = list()

    # 入栈    
    def push(self, item):
        self.items.append(item)

    # 出栈    
    def pop(self):
        return self.items.pop()

    # 清空栈   
    def clear(self):
        del self.items[:]

    # 判断栈是否为空   
    def empty(self):
        return self.size() == 0

    # 获取栈的大小    
    def size(self):
        return len(self.items)

    # 获取栈顶的节点   
    def top(self):
        return self.items[self.size() - 1]

def tarjan(u):
    global s, num, n, count, flag, stack, pre, low, matrix
    count = count + 1                       #次序编号加1
    pre[u] = low[u] = count                 #初始化节点u被搜索时和能回溯到的最早的祖先的次序
    s.push(u)                               #将节点u入栈
    flag[u] = True                          #将节点u标记为已在栈中
    for i in range(n):                      #循环矩阵图
        if matrix[u][i] == 0:               #若节点u没有指向节点i(为1是有指向)，则
            continue                        #跳出本次循环，进入下一循环
        # 若被指向节点i被标记为已在栈中，说明节点i已被访问过，则
        if flag.get(i, False) is True:      
            if (pre[i] < low[u]):           #若节点i的搜索次序<节点u的祖先次序，则
                low[u] = pre[i]             #更新节点u的祖先次序为节点i的搜索次序
        # 若被指向节点i被标记为不在栈中，说明节点i未被访问过，则
        else:                               
            tarjan(i)                       #递归下找
            low[u] = min(low[u], low[i])    #更新节点u的祖先次序为节点u和i的祖先次序中更小的
    # 若当前节点被搜索时和能回溯到的最早的祖先的次序相同，且栈不为空，则
    if (pre[u] == low[u] and s.empty() is False):   
       print("********连通图********")
       m = s.pop()                          #弹出栈中顶点m
       flag[m] = False                      #将节点m标记为不在栈中
       print(m)                             #打印该强连通分量中的节点
       # 当栈中弹出的顶点与当前节点不在同一联通分支，且栈不为空时循环
       while m != u and s.empty() is False: 
           num = num + 1                    #连通图数量+1
           m = s.pop()                      #继续弹出栈中顶点m
           flag[m] = False                  #将节点标记为不在栈中
           print(m)                         #打印该强连通分量中的节点
       print("*********************")  

矩阵图及指向：

[图片上传失败...(image-45030d-1567169657592)]

if __name__ == "__main__":
    matrix = [[0, 1, 1, 0, 0, 0], [0, 0, 0, 1, 0, 0], [0, 0, 0, 1, 1, 0], [1, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 0, 0]]#初始化矩阵图
    pre = OrderedDict()                     #顶点的搜索次序
    low = OrderedDict()                     #顶点能回溯到的最早的祖先的次序
    flag = dict()                           #标记节点是否已在栈中
    count = 0                               #初始化次序编号为0
    n = len(matrix)                         #获取矩阵图的长度
    num = 0                                 #初始化连通图数量
    s = Stack()                             #实例化栈类
    tarjan(3)                               #Tarjan算法，起点为节点3
    print("连通图数量为：%s" % num)

结果为：

********连通图********
5
*********************
********连通图********
4
*********************
********连通图********
5
*********************
********连通图********
2
1
0
3
*********************
连通图数量为：3

Gabow算法：
是Tarjan算法的提升版本，该算法类似于Tarjan算法。算法维护了一个顶点栈，但是还是用了第二个栈来确定何时从第一个栈中弹出各个强分支中的顶点，它的功能类似于Tarjan算法中的数组low。从起始顶点w处开始进行DFS过程中，当一条回路显示这组顶点都属于同一个强连通分支时，就会弹出栈二中顶点，只留下回边的目的顶点，也即搜索的起点w。当回溯到递归起始顶点w时，如果此时该顶点在栈二顶部，则说明该顶点是一个强联通分量的起始顶点，那么在该顶点之后搜索的顶点都属于同一个强连通分支。于是，从第一个栈中弹出这些点，形成一个强连通分支。