BFS Is breadth traversal , That is, the search is expanded layer by layer , First, find the first floor , Look for the second floor , Then find the third floor ... The data structure used is queue , First visit the first node , Then access all its adjacency points , Then access the adjacency point of the adjacency point , In the process , Ensure that the visited points are not accessed repeatedly .
DFS Is depth traversal , Start at a point , Gradually follow a path down , When we find the end , Go back to the previous node , Keep looking for ... The data structure used is stack , The next node accessed is an adjacent node of the current node , Then access its adjacent nodes .
Here's a picture , We use python Achieve depth and breadth traversal
graph = {
'A':['B','C'],
'B':['A','C','D'],
'C':['A','B','D','E'],
'D':['B','C','E','F'],
'E':['C','D'],
'F':['D']
}
def BFS(graph,s):
# Use queues to store elements of each layer
queue = []
seen = set()
queue.append(s)
seen.add(s)
# parent = {s : None}
while (len(queue) > 0):
# Represents vertices that pop up each time
vertex = queue.pop(0)
nodes = graph[vertex]
for w in nodes:
if w not in seen:
queue.append(w)
seen.add(w)
print(vertex, end = " ")
BFS(graph,'A')
def DFS(graph,s):
# Use stack , The next point is the adjacent point of the current point .
stack = []
seen = set()
queue.append(s)
seen.add(s)
# parent = {s : None}
while (len(queue) > 0):
# Represents vertices that pop up each time
vertex = queue.pop(0)
nodes = graph[vertex]
for w in nodes:
if w not in seen:
queue.append(w)
seen.add(w)
print(vertex, end =" ")
BFS(graph,'A')
