深度优先和广度优先

发表于 | 分类于 | |
字数统计: 1,327 | 阅读时长 ≈ 5

Depth-First Search和Breadth-First Search，即深度优先和广度优先是图的两种搜索的方法。其实与其说是方法，不如说是两种思想。下面我们就来介绍这两种思想。

深度优先是指在图的查找中，对每一个分支深入到不能再深入为止，如果到达了终点，则选择另一个未访问的顶点，继续查找，知道每个节点都被访问到，并且每个节点只能被访问一次。

基本算法：

a） 访问顶点V

b） 依次从V的未访问的节点出发，遍历所有与V在相通路径上的节点。

c） 选取还未被访问的结点，重复上面的过程。

下图就是深度优先的一个遍历过程。
DFS

广度优先是分层次的展开检查图中的所有结点，知道找到最终的结果。也就是说首先搜索与s距离为k的所有结点，然后在搜索与s距离k+1的所有结点。算法通过已找到的节点和未找到的节点的边界向外扩展。Dijkstra算法以及prim算法都是应用的这一思想。

下图就是广度优先的一个遍历过程。
BFS

下面是代码的python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#coding=utf-8 
class Gragh():
    def __init__(self,nodes,sides):
        '''
        nodes 表示点
        sides 表示边
        
        '''
        # self.sequense是字典，key是点，value是与key相连接的点
        self.sequense = {}
        # self.side是临时变量，主要用于保存与指定点相连接的点
        self.side=[]
        for node in nodes:
            for side in sides:
                u,v=side
                # 指定点与另一个点在同一个边中，则说明这个点与指定点是相连接的点，则需要将这个点放到self.side中
                if node ==u:
                    self.side.append(v)
                elif node == v:
                    self.side.append(u)
            self.sequense[node] = self.side
            self.side=[]
        #print self.sequense
        
    
    '''
    # Depth-First-Search 
        深度优先算法，是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。
        当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。
        这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，
        则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。        
    '''
    def DFS(self,node0):
        #queue本质上是堆栈，用来存放需要进行遍历的数据
        #order里面存放的是具体的访问路径
        queue,order=[],[]
        #首先将初始遍历的节点放到queue中，表示将要从这个点开始遍历
        queue.append(node0)
        while queue:
            #从queue中pop出点v，然后从v点开始遍历了，所以可以将这个点pop出，然后将其放入order中
            #这里才是最有用的地方，pop（）表示弹出栈顶，由于下面的for循环不断的访问子节点，并将子节点压入堆栈，
            #也就保证了每次的栈顶弹出的顺序是下面的节点
            v = queue.pop()
            order.append(v)
            #这里开始遍历v的子节点
            for w in self.sequense[v]:
                #w既不属于queue也不属于order，意味着这个点没被访问过，所以讲起放到queue中，然后后续进行访问
                if w not in order and w not in queue: 
                    queue.append(w)
        return order
    
    '''
     readth-First-Search
     BFS是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。
           广度优先搜索的实现一般采用open-closed表。
    '''
    def BFS(self,node0):
        #queue本质上是堆栈，用来存放需要进行遍历的数据
        #order里面存放的是具体的访问路径
        queue,order = [],[]
        #首先将初始遍历的节点放到queue中，表示将要从这个点开始遍历
        # 由于是广度优先，也就是先访问初始节点的所有的子节点，所以可以
        queue.append(node0)
        order.append(node0)
        while queue:
            #queue.pop(0)意味着是队列的方式出元素，就是先进先出，而下面的for循环将节点v的所有子节点
            #放到queue中，所以queue.pop(0)就实现了每次访问都是先将元素的子节点访问完毕，而不是优先叶子节点
            v = queue.pop(0)
            for w in self.sequense[v]:
                if w not in order:
                    # 这里可以直接order.append(w) 因为广度优先就是先访问节点的所有下级子节点，所以可以
                    # 将self.sequense[v]的值直接全部先给到order
                    order.append(w)
                    queue.append(w)
        return order
            
        


def main():  
    nodes = [i+1 for i in xrange(8)]

    sides=[(1, 2),
        (1, 3),
        (2, 4),
        (2, 5),
        (4, 8),
        (5, 8),
        (3, 6),
        (3, 7),
        (6, 7)]
    G = Gragh(nodes,sides)
    print G.DFS(1)
    print G.BFS(1)
    print G.DFS1(1)

if __name__ == "__main__":
    main()
显示 Gitment 评论