Shulou(Shulou.com)05/31 Report--

This article mainly explains "Python how to achieve the breadth and depth-first path search algorithm", interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Next let the editor to take you to learn "Python how to achieve the breadth and depth-first path search algorithm"!

Preface

A graph is an abstract data structure, which is essentially the same as a tree structure.

Compared with the tree, the graph is closed, and the tree structure can be regarded as the predecessor of the graph structure. In the tree structure, if the sibling nodes or child nodes are connected horizontally, it is built into a graph.

Trees are suitable for describing top-down one-to-many data structures, such as the organizational structure of a company.

The graph is suitable for describing more complex many-to-many data structures, such as complex group social relationships.

1. Graph theory

When solving problems in the real world with the help of computers, in addition to storing information in the real world, it is also necessary to correctly describe the relationship between information.

For example, when developing a map program, it is necessary to correctly simulate the relationship between the city and the city, or the roads in the city. On this basis, it is possible to calculate the best path from one city to another or from the specified starting point to the target point through the algorithm.

Similarly, there are flight maps, train maps, and social communication maps.

The graph structure can well map the complex relationship between the above information in the real world. By using this algorithm, we can easily calculate the shortest path in the flight line, such as the best transit scheme in the train line, such as who has the best relationship with whom in the social circle and who is the best match with whom in the marriage network.

1.1 the concept of graph

Vertex: a vertex is also called a node, but a graph can be thought of as a collection of vertices. The vertex itself has data meaning, so the vertex will carry additional information, called "payload".

The pinnacle can be a real-world city, place name, station name, person.

Edges: edges in a graph are used to describe the relationship between vertices. The edge can have direction or no direction, and the edge with direction can be divided into one-way edge and two-way edge.

The edge between the following figure (item point 1) and (vertex 2) has only one direction (the direction shown by the arrow), which is called an one-way edge. Similar to the one-way road in the real world.

The edges between (vertex 1) and (vertex 2) have two directions (two-way arrows), which are called two-way edges. The relationship between city and city is two-way.

Weight: value-added information can be added on the edge, and the additional value is called weight. Weighted edges are used to describe the strength of the connection from one vertex to another.

For example, in a subway line in real life, the weight can describe the length of time, mileage and fare between two stations.

Edges describe the relationship between vertices, and weights describe the differences of connections.

Path:

First understand the concept of path in the real world.

For example, if you drive from one city to another, you need to determine the path first. That is, which cities do I have to go through from the point of departure to the destination? How many miles does it take?

It can be said that a path is a sequence of vertices connected by edges. Because there is more than one path, the description of the path from one item point to another does not refer to one.

How to calculate the path in the graph structure?

The length of the unweighted path is the number of sides on the path.

The length of the weighted path is the sum of the weights of the edges on the path.

As shown above, the length of the path from (vertex 1) to (vertex 3) is 8.

Ring: starting from the starting point, and finally back to the starting point (the end is also the starting point) will form a ring, the ring is a special path. As above (V1, V2, V3, V1) is a ring.

Type of graph:

To sum up, graphs can be divided into the following categories:

Directed graph: a graph whose edge has a direction is called a directed graph.

Undirected graph: a graph whose edge has no direction is called an undirected graph.

Weighted graph: a graph with weight information on the edge is called a weighted graph.

Acyclic graph: a graph without a ring is called an acyclic graph.

Directed acyclic graph: a directed graph without a ring, referred to as DAG.

1.2 definition diagram

According to the characteristics of the graph, the graph data structure should contain at least two types of information:

All vertices form a set of information, which is represented by V here (for example, in a map program, all cities are constructed in a vertex set).

All edges form set information, which is represented here by E (description of the relationship between cities).

How do you describe edges?

Edges are used to represent the relationship between item points. So an edge can include 3 metadata (start point, end point, weight). Of course, the weight can be omitted, but the general study of the graph, refers to the weighted graph.

If the graph is represented by G, then G = (V, E). Each edge can be described as either a fv,ev or a fv,ev,w.

Fv represents the starting point and ev represents the end point. And the fv,ev data must be referenced in the V collection.

The structure of the figure above can be described as follows:

# 5 vertices V = {A0rect B1, C2, D3, and E4} # 7 edges E = {(A0), (B1), (B1), (C2), (C2, E4, 1), (D3, E4, 2), (A0, D3, 5), (E4, B1, 7)} 1.3 abstract data structure

There must be at least one method in the abstract data description of the diagram:

Graph (): used to create a new graph.

Add_vertex (vert): add a new node to the diagram, and the parameter should be an object of node type.

Add_edge (fv,tv): an edge relationship is established between two item points.

Add_edge (fv,tv,w): establishes an edge between 2 item points and specifies the connection weight.

Find_vertex (key): finds vertices in the graph based on the keyword key.

Find_vertexs (): query all vertex information.

Find_path (fv,tv): find. The path from one vertex to another.

two。 Storage implementation of Graph

There are two main storage implementations of graphs: adjacency matrix and linked table. This paper mainly introduces adjacency matrix.

2.1 adjacency matrix

Use a two-dimensional matrix (array) to store the relationship between vertices.

For example, graph [5] [5] can store the relational data of five vertices. The row number and column number represent the vertex, and the value in the cell crossed in the w column of row v represents the weight from vertex v to vertex w. For example, grap [2] [3] = 6 indicates the connection (adjacent) of C2 vertex and D3 vertex, and the weight is 6.

The advantage of adjacent matrices is that they are simple and can clearly show that those vertices are connected. Because there is not a connection between every two vertices, it will result in a large amount of space idle, which is called "sparse".

The matrix fills up only when each vertex is related to the other vertices. Therefore, using this structure to store graph data will result in a lot of space waste for the graph structure whose relationship is not very complex.

Adjacency matrix is suitable for representing complex graph structures, such as links between web pages on the Internet, social relations between people in social circles.

2.2 Encoding to realize adjacency Matrix

Because the vertex itself has data meaning, it is necessary to define the vertex type first.

Vertex class:

"" class Vertex: def _ _ init__ (self, name) V_id=0): # Vertex number self.v_id = v_id # Vertex name self.v_name = name # whether it has been accessed: False has no True: there is self.visited = False # self-display def _ _ str__ (self): return'[number is {0} Vertex '.format (self.v_id, self.v_name) named {1}]

V_id and v_name in vertex classes are easy to understand. Why add a visited?

This variable is used to record whether vertices have been searched during the path search process to avoid repeated search calculations.

Graph class: there are many methods of graph class, which are introduced here one by one.

Initialization method

Class Graph: "nums: size of adjacent matrix" def _ init__ (self, nums): # one-dimensional list, save nodes, there can only be a maximum of nums nodes self.vert_list = [] # two-dimensional list, store vertices and the relationship between vertices (weight) # initial weight is 0 Indicates that no relationship has been established between nodes self.matrix = [[0] * nums for _ in range (nums)] # number of vertices self.v_nums = 0 # use queues to simulate queues or stacks For breadth-first, depth-first search algorithm self.queue_stack = [] # Save the searched path self.searchPath = [] # temporarily omitted.

The initialization method is used to initialize the data types in the diagram:

One-dimensional list vert_list saves all vertex data.

2D list matrix saves data about the relationship between vertices and vertices.

Queue_stack uses lists to simulate queues or stacks for subsequent breadth and depth searches.

How do I use a list to simulate a queue or stack?

There are two valuable methods on the list, append () and pop ().

Append () is used to add data to the list, each time from the bottom of the list.

Pop () removes and pops data from the bottom of the list by default, and pop (parameter) provides an index value for deleting and popping up data from a specified location.

Using the append () and pop () methods, you can simulate the stack and move in and out of the data from the same place.

Using the append () and pop (0) methods, you can simulate the queue, add data from behind, and get data from the front.

SearchPath: used to save results from searches using breadth or depth-first paths.

Add a new section (top) method:

"" add a new vertex "" def add_vertex (self Vert): if vert in self.vert_list: # already exists return if self.v_nums > = len (self.matrix): # exceeds the upper limit of nodes that can be stored in an adjacent matrix return # the number of vertices is internally generated vert.v_id = self.v_nums self.vert_list .append (vert) # increase the quantity by one self.v_nums + = 1

Note that the node numbering is provided by the internal logic of the diagram, which is convenient for the unification of the node numbering sequence.

Add Edge method

This method is the core logic of adjacency matrix representation.

'' add the edge between the node and the node, if it is an unauthorized regraph Uniformly set to 1''def add_edge (self, from_v, to_v): # if the node does not exist if from_v not in self.vert_list: self.add_vertex (from_v) if to_v not in self.vert_list: self.add_vertex (to_v) # the number of the from_v node is the line number The to_v node is numbered as column number self.matrix [from _ v.v_id] [to_v.v_id] = 1''add weighted edges' 'def add_edge (self, from_v, to_v Weight): # if the node does not exist if from_v not in self.vert_list: self.add_vertex (from_v) if to_v not in self.vert_list: self.add_vertex (to_v) # the number of the from_v node is the line number The number of the to_v node is self.matrix [from _ v.v_id] [to_v.v_id] = weight

There are two ways to add edge information, one to add unauthorized edges and one to add weighted edges.

Find a node

Use the linear lookup method to find a node from the node collection.

Def find_vertex (self, v_id): if v_id > = 0 or v_id according to the node number

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.