Breadth first and depth first search algorithm examples for graphs of Python data structures and algorithms

This paper illustrates the breadth - first and depth - first search algorithm of Python data structure and algorithm graph. To share for your reference, specific as follows:

According to the pseudo-code of Wikipedia:

Breadth first BFS:

Use queues, collections

Mark that the initial node has been found and put into the queue

Each loop ejects 1 node from the queue

Queue all the connected nodes of the node and mark that they have been found

Through the queue, open all the doors at the maze intersection, enter through one door, continue to open the inside door, and then return to the first door

"""
 procedure BFS(G,v) is
   let Q be a queue
   Q.enqueue(v)
   label v as discovered
   while Q is not empty
    v  please  Q.dequeue()
    procedure(v)
    for all edges from v to w in G.adjacentEdges(v) do
      if w is not labeled as discovered
        Q.enqueue(w)
        label w as discovered
"""
def procedure(v):
  pass
def BFS(G,v0):
  """  Breadth first search  """
  q, s = [], set()
  q.extend(v0)
  s.add(v0)
  while q:  #  When the queue q Is not empty 
    v = q.pop(0)
    procedure(v)
    for w in G[v]:   #  The figure G The vertices v All adjacent points w
      if w not in s: #  If the vertices  w  Has not been found 
        q.extend(w)
        s.add(w)  #  record w Has been found 

Depth priority DFS

Using stacks, collections

Initial node push

Each cycle pops 1 node from the stack and marks it as found

For each popup node, put all the connected nodes in the queue

Through the structure of the stack, 1 step by step deep excavation

""""
Pseudocode[edit]
Input: A graph G and a vertex v of G
Output: All vertices reachable from v labeled as discovered
A recursive implementation of DFS:[5]
1 procedure DFS(G,v):
2   label v as discovered
3   for all edges from v to w in G.adjacentEdges(v) do
4     if vertex w is not labeled as discovered then
5       recursively call DFS(G,w)
A non-recursive implementation of DFS:[6]
1 procedure DFS-iterative(G,v):
2   let S be a stack
3   S.push(v)
4   while S is not empty
5      v = S.pop()
6      if v is not labeled as discovered:
7        label v as discovered
8        for all edges from v to w in G.adjacentEdges(v) do
9          S.push(w)
"""
def DFS(G,v0):
  S = []
  S.append(v0)
  label = set()
  while S:
    v = S.pop()
    if v not in label:
      label.add(v)
      procedure(v)
      for w in G[v]:
        S.append(w)

For more information about Python, please refer to Python Data Structure and Algorithm Tutorial, Python Encryption and Decryption Algorithm and Skills Summary, Python Coding skills Summary, Python Function Use Skills Summary, Python String Manipulation Skills Summary and Python Introduction and Advanced Classic Tutorial.

I hope this article has been helpful in Python programming.