本文共 5962 字，大约阅读时间需要 19 分钟。
golang数据结构
A graph is a representation of a network structure. There are tons of graph real world examples, the Internet and the social graph being the classic ones.
图是网络结构的表示。 有大量的图现实世界示例，互联网和社交图就是经典的例子。
It’s basically a set of nodes connected by edges.
它基本上是由edge连接的一组节点 。
I’ll skip the mathematical concepts since you can find them everywhere and jump directly to a Go implementation of a graph.
我将跳过数学概念，因为您可以在任何地方找到它们，然后直接跳转到图的Go实现。
A graph data structure will expose those methods:
图形数据结构将公开这些方法：
AddNode() inserts a node
AddNode()插入一个节点
AddEdge() adds an edge between two nodes
AddEdge()在两个节点之间添加一条边
and String() for inspection purposes.
和String()用于检查目的。
A Graph is defined as
图定义为
type ItemGraph struct { nodes []*Node edges map[Node][]*Node lock sync.RWMutex} with Node being
与节点是
type Node struct { value Item} I’ll implement an undirected graph, which means that adding an edge from A to B also adds an edge from B to A.
我将实现一个无向图，这意味着从A到B添加一条边也会从B到A添加一条边。
// Package graph creates a ItemGraph data structure for the Item typepackage graphimport ( "fmt" "sync" "github.com/cheekybits/genny/generic")// Item the type of the binary search treetype Item generic.Type// Node a single node that composes the treetype Node struct { value Item}func (n *Node) String() string { return fmt.Sprintf("%v", n.value)}// ItemGraph the Items graphtype ItemGraph struct { nodes []*Node edges map[Node][]*Node lock sync.RWMutex}// AddNode adds a node to the graphfunc (g *ItemGraph) AddNode(n *Node) { g.lock.Lock() g.nodes = append(g.nodes, n) g.lock.Unlock()}// AddEdge adds an edge to the graphfunc (g *ItemGraph) AddEdge(n1, n2 *Node) { g.lock.Lock() if g.edges == nil { g.edges = make(map[Node][]*Node) } g.edges[*n1] = append(g.edges[*n1], n2) g.edges[*n2] = append(g.edges[*n2], n1) g.lock.Unlock()}// AddEdge adds an edge to the graphfunc (g *ItemGraph) String() { g.lock.RLock() s := "" for i := 0; i < len(g.nodes); i++ { s += g.nodes[i].String() + " -> " near := g.edges[*g.nodes[i]] for j := 0; j < len(near); j++ { s += near[j].String() + " " } s += "\n" } fmt.Println(s) g.lock.RUnlock()} Quite straightforward. Here’s a test that when run, will populate the graph and print
非常简单。 这是一个测试，运行时将填充图形并打印
$ go testA -> B C DB -> A EC -> A ED -> AE -> B C FF -> EPASS
package graphimport ( "fmt" "testing")var g ItemGraphfunc fillGraph() { nA := Node{"A"} nB := Node{"B"} nC := Node{"C"} nD := Node{"D"} nE := Node{"E"} nF := Node{"F"} g.AddNode(&nA) g.AddNode(&nB) g.AddNode(&nC) g.AddNode(&nD) g.AddNode(&nE) g.AddNode(&nF) g.AddEdge(&nA, &nB) g.AddEdge(&nA, &nC) g.AddEdge(&nB, &nE) g.AddEdge(&nC, &nE) g.AddEdge(&nE, &nF) g.AddEdge(&nD, &nA)}func TestAdd(t *testing.T) { fillGraph() g.String()} BFS (Breadth-First Search) is one of the most widely known algorithm to traverse a graph. Starting from a node, it first traverses all its directly linked nodes, then processes the nodes linked to those, and so on.
BFS (宽度优先搜索)是遍历图形的最广为人知的算法之一。 从节点开始，它首先遍历其所有直接链接的节点，然后处理链接到这些节点的节点，依此类推。
It’s implemented using a queue, which is generated from my with code generation for the node type:
它是使用队列实现的，该队列是从我生成的，并为节点类型生成了代码：
// This file was automatically generated by genny.// Any changes will be lost if this file is regenerated.// see https://github.com/cheekybits/gennypackage graphimport "sync"// NodeQueue the queue of Nodestype NodeQueue struct { items []Node lock sync.RWMutex}// New creates a new NodeQueuefunc (s *NodeQueue) New() *NodeQueue { s.lock.Lock() s.items = []Node{} s.lock.Unlock() return s}// Enqueue adds an Node to the end of the queuefunc (s *NodeQueue) Enqueue(t Node) { s.lock.Lock() s.items = append(s.items, t) s.lock.Unlock()}// Dequeue removes an Node from the start of the queuefunc (s *NodeQueue) Dequeue() *Node { s.lock.Lock() item := s.items[0] s.items = s.items[1:len(s.items)] s.lock.Unlock() return &item}// Front returns the item next in the queue, without removing itfunc (s *NodeQueue) Front() *Node { s.lock.RLock() item := s.items[0] s.lock.RUnlock() return &item}// IsEmpty returns true if the queue is emptyfunc (s *NodeQueue) IsEmpty() bool { s.lock.RLock() defer s.lock.RUnlock() return len(s.items) == 0}// Size returns the number of Nodes in the queuefunc (s *NodeQueue) Size() int { s.lock.RLock() defer s.lock.RUnlock() return len(s.items)} Here’s the BFS implementation:
这是BFS的实现：
// Traverse implements the BFS traversing algorithmfunc (g *ItemGraph) Traverse(f func(*Node)) { g.lock.RLock() q := NodeQueue{} q.New() n := g.nodes[0] q.Enqueue(*n) visited := make(map[*Node]bool) for { if q.IsEmpty() { break } node := q.Dequeue() visited[node] = true near := g.edges[*node] for i := 0; i < len(near); i++ { j := near[i] if !visited[j] { q.Enqueue(*j) visited[j] = true } } if f != nil { f(node) } } g.lock.RUnlock()} which can be tested with
可以用
func TestTraverse(t *testing.T) { g.Traverse(func(n *Node) { fmt.Printf("%v\n", n) })} which after being added to our tests, will print the road it took to traverse all our nodes:
在添加到我们的测试中之后，它将打印遍历我们所有节点所花费的道路：
ABCDAEF
You can use this generic implemenation to generate type-specific graphs, using
您可以使用以下通用实现来生成特定于类型的图，方法是：
//generate a `IntGraph` graph of `int` valuesgenny -in graph.go -out graph-int.go gen "Item=int"//generate a `StringGraph` graph of `string` valuesgenny -in graph.go -out graph-string.go gen "Item=string"
翻译自:
golang数据结构
转载地址：http://iaqgb.baihongyu.com/