一、图的概念和存储方法
这篇博客写的非常详细,暂时没有想到什么要补充的,就把链接直接放在这吧,如果以后有补充,再将内容记录在这里吧。
https://blog.csdn.net/qq_21201267/article/details/90758656
二、BFS、DFS原理及python实现
1、BFS(广度优先搜索)
原理:
其原理直白的说就是在搜索完第k层的节点之前,不会搜索第k+1层的节点的。
BFS过程,就是建造一棵以顶点 s 为根的树的过程,一次建造树的一层,同时,BFS在增加k+1层次之前,会保证将所有的k层的子顶点都添加在了树中。
实现思路:
1、利用队列实现
2、从源节点开始依次按照宽度进队列,然后弹出
3、每弹出一个节点,就把该节点所有没有进过队列的邻接点放入队列
4、直到队列变空
python代码
from queue import Queue
def bfs(node):
if node is None:
return
queue = Queue()
nodeSet = set()
queue.put(node)
nodeSet.add(node)
while not queue.empty():
cur = queue.get() # 弹出元素
print(cur.value) # 打印元素值
for next in cur.nexts: # 遍历元素的邻接节点
if next not in nodeSet: # 若邻接节点没有入过队,加入队列并登记
nodeSet.add(next)
queue.put(next)
2、DFS(深度优先搜索)
原理:
直白的说,就是一条路走到底,发现都访问过了,还没找到,返回到上一个岔路口,继续查找。
实现思路:
1、利用栈实现
2、从源节点开始把节点按照深度放入栈,然后弹出
3、每弹出一个点,把该节点下一个没有进过栈的邻接点放入栈
4、直到栈变空
python代码:
def dfs(node):
if node is None:
return
nodeSet = set()
stack = []
print(node.value)
nodeSet.add(node)
stack.append(node)
while len(stack) > 0:
cur = stack.pop() # 弹出最近入栈的节点
for next in cur.nexts: # 遍历该节点的邻接节点
if next not in nodeSet: # 如果邻接节点不重复
stack.append(cur) # 把节点压入
stack.append(next) # 把邻接节点压入
set.add(next) # 登记节点
print(next.value) # 打印节点值
break # 退出,保持深度优先
参考:
https://www.jianshu.com/p/a46ee4ed2a8f