极客算法

广度优先搜索算法BFS

2020-05-21
Algorithm
 

宽度优先搜索

宽度优先搜索。是把最近的邻居节点都访问之后，在选择更远邻居的一种策略。很像把一块石头丢到水里，水波纹一层层向外扩散的过程。所以宽度优先搜索，更形象的称之为层级搜索

非递归代码，通过队列Queue来完成。考虑到递归的缺点，加上BFS实现简单, BFS一般不用递归来实现

BFS适用于：层级遍历，图是否连通，拓扑排序，(同权重)最短路径

树与图

图的遍历，一定，一定，一定要去重复，重要的事情说三遍

树的遍历，就不需要去重复，因为根据树的定义，不可能有环出现

图是树的充分必要条件：

  1. N个点，N-1条边
  2. 所有点连通

图的表示

社交网络是图比较常用的切入话题之一，包括N度人脉，单向关注，好友关系

graph_representation

edge(i, j)表示从点i到点j有一条边

边列表(edge lists)

每一个二元组代表，两个顶点之前有一条边，对于不连通的图，还需配合顶点列表List

[ [0,1], [0,6], [0,8], [1,4], [1,6], [1,9], [2,4], [2,6], [3,4], [3,5],
[3,8], [4,5], [4,9], [7,8], [7,9] ]

临接表(adjacency lists)

# 比较常用
[ [1, 6, 8],     # 0 -> [1,6,8]   # edge(0, 1), edge(0, 6), edge(0, 8)
  [0, 4, 6, 9],  # 1 -> [0,4,6,9] # edge(1, 0), edge(1, 4), edge(1, 6), edge(1, 9)
  [4, 6],
  [4, 5, 8],
  [1, 2, 3, 5, 9],
  [3, 4],
  [0, 1, 2],
  [8, 9],
  [0, 3, 7],
  [1, 4, 7] ]

邻接矩阵(adjacency matrices)

# edge(i,j) = M[i][j] = 1, 比较浪费存储
[ [0, 1, 0, 0, 0, 0, 1, 0, 1, 0],
  [1, 0, 0, 0, 1, 0, 1, 0, 0, 1],
  [0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
  [0, 0, 0, 0, 1, 1, 0, 0, 1, 0],
  [0, 1, 1, 1, 0, 1, 0, 0, 0, 1],
  [0, 0, 0, 1, 1, 0, 0, 0, 0, 0],
  [1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
  [1, 0, 0, 1, 0, 0, 0, 1, 0, 0],
  [0, 1, 0, 0, 1, 0, 0, 1, 0, 0] ]

数据结构的存储

内存中的数据结构，类等，通常无法直接用来网络传输，或存储在磁盘上，要通过序列化之后进行

序列化：

object_to_string: 将内存中的数据结构，类等转化成字符串(字节组数)的过程

反序列化：

string_to_object: 将序列化结果，从新解析成对应数据结构的过程

常见的序列化有xml, json, protobuf, thrift, yaml, plist

设计权衡通常有可读性，压缩率

数据结构的拷贝

拷贝只对于复合数据结构(数组，类)才有所不同, 虽然不同语言处理细节不同, 但简单原则如下:

浅拷贝(reference)

尽可能拷贝的越少越好，无论是否返回​同一个对象，最终的数据源是共享的，一份数据的改变体现在所有的拷贝上

A = C0
B = copy(A) = C0
# 如果C改变，那么B的状态也会改变

深拷贝(clone)

拷贝所有细节，返回不同的对象，最终的数据源是隔离的，一份数据的改变不会影响其他拷贝

深拷贝有潜在的诸多问题:

  1. 拷贝内容过多, 通常解决的方案，是让开发者自己定义如何拷贝。
  2. 循环拷贝, 属于图的遍历范畴，所以记得去重复。
A = C0
B = deepcopy(A) = C1
# 如果C0改变，B的状态C1没有影响

拓扑排序

1 ->
       3  -> 4 -> 5
2 ->

# 拓扑序列: [1, 2 ,3, 4, 5] 或 [2, 1, 3, 4, 5]

对于有向无环图(DAG), 至少有一个拓扑排序。

拓扑排序主要对于有依赖关系的一组任务，给出一个可执行的序列。此外拓扑排序还可以判断有没有循环依赖， 比如编译循环依赖检测，内存泄漏等问题。

常见的问题有，对于给定的一组依赖关系，有没有可能拓扑排序，如果有，输出其中一个结果

课程排序

# leetcode-210(Course-Schedule-II)
# 现在你总共有 n 门课需要选，记为 0 到 n-1。
# 在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
# 给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。
# 可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。
from collections import Counter, deque
class Solution(object):
    def findOrder(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: List[int]
        """
        res = []
        indegrees = Counter()
        edges = defaultdict(list)
        
        for pair in prerequisites:
            indegrees[pair[0]] += 1
            edges[pair[1]].append(pair[0])
            
        queue = deque()
        for i in range(numCourses):
            if indegrees[i] == 0:
                queue.append(i)
                
        while(len(queue) > 0):
            front = queue.popleft()
            res.append(front)

            for neighbor in edges[front]:
                indegrees[neighbor] -= 1
                if indegrees[neighbor] == 0:
                    queue.append(neighbor)
                    del indegrees[neighbor]
                    
        return [] if len(indegrees) > 0 else res

–End–

上一篇 二叉树与分治算法

下一篇 深度优先搜索算法DFS

评论

内容:
其他: