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

This article introduces the relevant knowledge of "how to achieve breadth and depth-first search in go language". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

The realization of Graph

A graph is a collection of nodes and their connections. Therefore, nodes can be represented by an one-dimensional array, and the relationship between nodes can be represented by a two-dimensional array.

/ / Matrix implementation of typedef struct MGRAPH {nodes int []; / / Node edges int [] []; / / Edge} mGraph

However, for some practical problems, there may be a large number of zero values in the adjacency matrix, and the sparse graph can be represented by the adjacency linked list, and its data structure is shown in the figure.

On the left is the diagram of the diagram, and on the right is the adjacency list of the diagram. The scarlet letter represents the node sequence number, and the linked list is the node connected to this node, such as 1 node connected to 2 or 5 nodes. Because in go, arrays can be easily used instead of linked lists, the linked list structure can be written as

Package mainimport "fmt" type Node struct {value int; / / node is int}; type Graph struct {nodes [] * Node edges map [Node] [] * Node / / adjacency representation of undirected graph}

Where map is the key value index type in Go language, and its definition format is map [], which is the key and the value. In the graph structure, map [Node] [] * Node represents an array of Node corresponding to a Node pointer.

The following will generate a diagram through the Go language

/ / add node / / it can be understood as Graph member function func (g * Graph) AddNode (n * Node) {g.nodes = append (g.nodes, n)} / / add edge func (g * Graph) AddEdge (u, v * Node) {g.edges [* u] = append (g.edges [* u], v) / / u-> v edge g.edges [* v] = append (g.edges [* v]) U) / / u-> v side} / / print the graph func (g * Graph) Print () {/ / range traversing g.nodes Returns the index and values for _, iNode:=range g.nodes {fmt.Printf ("% v:", iNode.value) for _, next:=range g.edges [* iNode] {fmt.Printf ("% v->") Next.value)} fmt.Printf ("\ n")}} func initGraph () Graph {g: = Graph {} for ifunc initGraph I5-> 2 BFS 1-> 3-> 4-> 5-> 3-> 4-> 5-> 3-> 4-> 4-> 4-> 4-> 4-> 5-> 5-> 5-> 5-> 5-> 1-> 2-> 4->

Breadth-first search (BFS) is the simplest graph search algorithm. After the source node of the graph is given, the breadth-first search is tentatively searched externally. Its characteristic is that the progress is controlled by the interval between the source node and the source node, that is, only when the node that is k k k away from the source node is searched, the search will continue to get the node with the distance from the source node to the source node.

For the search of a graph, there may be a problem of repetition, that is, if 1 searches to 2, and accordingly 2 to 1, there may be an endless loop. Therefore, for the nodes in the figure, we mark them with searched, and when the value is false, it means that it has not been searched, otherwise it has been searched.

Type Node struct {value int; searched bool;} / * func initGraph () Graph {g: = Graph {} * / change the node generation function for iV1 accordingly Iv edge g.edges [v] = append (g.edges [v], u) / / u-> v edge} / / print graph func (g * Graph) Print () {/ / range traversing g.nodes Returns the index and value for _, iNode:=range g.nodes {fmt.Printf ("% v:", iNode.value) for _, next:=range g.edges [iNode] {fmt.Printf ("% v->") Next.value)} fmt.Printf ("\ n")}} func initGraph () Graph {g: = Graph {} for ifunc initGraph I5-> 9-> 2 1-> 3-> 4-> 5-> 3-> 4-> 4-> 4-> 4-> 4-> 4-> 5-> 5-> 4-> 4-> 6-> 7-> 6-> 6-> 7-> 7-> 7-5-> 8-> 7-5-> 8-> 9-1-> / / the following is the BFS result: 1:2 5 92:3 4340 76:88:7:9:DFS.

The difference between depth-first traversal (DFS) and BFS is that the search process of the latter can be understood layer by layer, that is, the node we initially searched can be regarded as the parent node, then the node connected with this node is the first generation node, and then the second generation node is searched after searching the first generation node. DFS searches from the parent node to the last generation node to get a lineage of one last generation node, and then traverses all the nodes to find another lineage until there are no unsearched nodes.

The basic steps are:

First, select an unvisited vertex V0 as the initial vertex and mark it as visited

Then search all the vertices adjacent to V0 to determine whether they have been visited. If there are any vertices that have not been accessed, select a vertex V1 to access, and so on, until there are no unvisited nodes in the Vn Ventrn Vn.

If there are still some vertices in the graph that are not accessed, then select one of the vertices to access, otherwise the traversal ends.

Let's first implement the second step, that is, the deepest search results for a single node.

Func (g * Graph) visitNode (n * Node) {for _, iNode:= range g.edges [n] {if! iNode.searched {iNode.searched = true fmt.Printf ("% v->" INode.value) g.visitNode (iNode) return}} func main () {g: = initGraph () g.nodes [0] .searched = true fmt.Printf ("% v->", g.nodes [0] .value) g.visitNode (g.nodes [0])}

The result is

PS E:\ Code > go run.\ goGraph.go1- > 2-> 3-> 4-> 5-> 6-> 8->

That is,

It can be seen that there are nodes 7 and 9 that have not been accessed.

The complete DFS algorithm only needs to add a traversal of all nodes before traversing a single point.

Func (g * Graph) DFS () {for _, iNode:=range g.nodes {if! iNode.searched {iNode.searched = true fmt.Printf ("% v->" INode.value) g.visitNode (iNode) fmt.Printf ("\ n") g.DFS ()}} func main () {g: = initGraph () g.nodes [0] .searched = true fmt.Printf ("% v->" G.nodes [0] .value) g.visitNode (g.nodes [0])}

The result is

PS E:\ Code > go run.\ goGraph.go1- > 2-> 3-> 4-> 5-> 6-> 8-> 7-> 9-> "how to achieve breadth and depth-first search in go language" is introduced here. Thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

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.