Shulou(Shulou.com)06/03 Report--

This article mainly shows you the "python depth-first and breadth-first algorithm example analysis", the content is easy to understand, clear, hope to help you solve your doubts, the following let the editor lead you to study and learn "python depth-first and breadth-first algorithm example analysis" this article.

The details are as follows:

First of all, there is a concept: backtracking

Backtracking method (exploration and backtracking method) is a kind of optimal search method, which searches forward according to the optimal conditions in order to achieve the goal. However, when exploring a certain step, it is found that the original choice is not excellent or can not achieve the goal, then go back and choose again. The technique of going back again and again is the retrospective method, and the point of a certain state that meets the backtracking condition is called the "retrospective point".

Depth first algorithm:

(1) access the initial vertex v and mark that vertex v has been accessed.

(2) find the first adjacent vertex w of vertex v.

(3) if the adjacent vertex w of vertex v exists, continue execution; otherwise, go back to v and find another unvisited adjacency point of v.

(4) if vertex w has not been accessed, visit vertex w and mark vertex w as visited.

(5) continue to find the next adjacent vertex wi of vertex w, if v takes wi, go to step (3). Until all the vertices in the connected graph have been visited.

Breadth first algorithm:

(1) Vertex v is queued.

(2) continue execution when the queue is not empty, otherwise the algorithm ends.

(3) get out of the queue to get the vertex v of the queue head; access vertex v and mark that vertex v has been accessed.

(4) find the first adjacent vertex col of vertex v.

(5) if the adjacency vertex col of v has not been accessed, the col is queued.

(6) continue to find another new adjacency vertex col of vertex v, and go to step (5). Until all the unvisited adjacencies of vertex v are processed. Go to step (2).

Code:

#! / usr/bin/python#-*-coding: utf-8-*-class Graph (object): def _ init__ (self,*args,**kwargs): self.node_neighbors = {} self.visited = {} def add_nodes (self,nodelist): for node in nodelist: self.add_node (node) def add_node (self Node): if not node in self.nodes (): self.node_ self,edge [node] = [] def add_edge (node): U V = edge if (v not in self.node_ neighbors [u]) and (u not in self.node_ neighbors [v]): self.node_ neighbors [u] .append (v) if (upright cycles): self.node_ neighbors [v] .append (u) def nodes (self): return self.node_neighbors.keys () def depth_first_search (self) Root=None): order = [] def dfs (node): self.visited [node] = True order.append (node) for n in self.node_neighbors [node]: if not n in self.visited: dfs (n) if root: dfs (root) for node in self.nodes (): if not node in self.visited: dfs (node) print order return order def breadth_first_search (self Root=None): queue = [] order = [] def bfs (): while len (queue) > 0: node = queue.pop (0) self.visited [node] = True for n in self.node_neighbors [node]: if (not n in self.visited) and (not n in queue): queue.append (n) order.append (n) If root: queue.append (root) order.append (root) bfs () for node in self.nodes (): if not node in self.visited: queue.append (node) order.append (node) bfs () print order return orderif _ _ name__ ='_ _ main__': g = Graph () g.add_nodes ([item1 for i in range (8)]) g.add_edge ((1) 2)) g.add_edge ((1,3)) g.add_edge ((2,4)) g.add_edge ((2,5)) g.add_edge ((4,8)) g.add_edge ((5,8)) g.add_edge ((3,6)) g.add_edge ((3,7) g.add_edge ((6,7)) print "nodes:" G.nodes () order = g.breadth_first_search (1) order = g.depth_first_search (1)

Results:

Nodes: [1, 2, 3, 4, 5, 6, 7, 8]

Breadth first:

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

Depth first:

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

The above is all the contents of the article "example Analysis of depth-first and breadth-first algorithms in python". Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.