7.5通用的深度优先搜索

一般的深度优先搜索目标是在图上进行尽量深的搜索，连接尽量多的顶点，必要时可以进行分支（创建了树），有时候深度优先搜索会创建多棵树，称为“深度优先森林”
深度优先搜索同样要用到顶点的“前驱”属性，来构建树或森林另外要设置“发现时间”和“结束时间”属性
• 前者是在第几步访问到这个顶点（设置灰色）
• 后者是在第几步完成了此顶点探索（设置黑色）
这两个新属性对后面的图算法很重要

带有DFS算法的图实现为Graph的子类，顶点Vertex增加了成员Discovery及Finish，图Graph增加了成员time用于记录算法执行的步骤数目
通用的深度优先搜索算法代码：

from basicGraph import Graph


class DFSGraph(Graph):
    def __init__(self):
        super().__init__()
        

    def dfs(self):
        for v in self:
            v.setColor('white')
            v.setPred(None)
        for v in self:
            self.dfsvisit(v)

    def dfsvisit(self,startV):
        startV.setColor('gray')

        for nbr in startV.getConnections():
            if nbr.getColor() == 'white':
                nbr.setPred(startV)
                self.dfsvisit(nbr)

        startV.setColor('black')
        print(startV.getId())


if __name__ == '__main__':
    g = DFSGraph()
    for i in range(6):
        g.addVertex(i)


    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)

    g.dfs()