本文共 1082 字,大约阅读时间需要 3 分钟。
图是一般用来定义对象之间的关系或联系的模型。在图的基本算法中,最基础的就是遍历算法。我们根据访问节点的顺序不同可分为广度优先搜索BFS和深度优先搜索DFS。
简单来说,广度优先搜索的特点是在遍历图中顶点之前先访问当前顶点的所有邻接结点;深度优先搜索的特点是访问途中顶点后递归的访问此顶点的所有未访问过的相邻顶点。
因为时间关系,我仅仅用python实现了BFS广度优先搜索。代码贴在下面,不难很简单就不解释了。
#-*- coding:utf-8 -*-# 类似于树的层次遍历结构""":type num: int 结点的个数:type edges: List[List[int]] :rtype: List[int]"""import Queuedef bfs(num, edges, visited, start): queue = Queue.Queue() # 队列 queue.put(start) visited[start] = 1 while not queue.empty(): front = queue.get() print front for i in range(num): if (not visited[i]) and ([i, front] in edges): queue.put(i) visited[i] = 1 if __name__ == '__main__': num = 5 # 结点个数 edges = [[1,3],[2,3],[0,3],[0,1],[2,1],[1,2],[0,2],[0,4],[2,4]] # 结点的联系 visited = [0 for n in range(num)] # 已经访问过的点 for i in range(num): if visited[i] == 1: continue bfs(num, edges, visited, i)
P.S. edges数组中的元素表示的是结点与结点的联系,比如[1,3]表示的是结点3指向结点1。
转载地址:http://vhyii.baihongyu.com/