介绍
图是网络结构的表示。现实世界中有大量图谱示例,互联网和社交图谱就是经典示例。图基本上是一组由边连接的节点。
实现
实现思路
图形数据结构将实现这些方法:
AddNode():添加一个节点到图里
AddEdge():添加一条边到图里
Print():打印图结构
图结构定义为:
type Graph struct {sync.RWMutexnodes []*Nodeedges map[Node][]*Node
}
节点定义为:
import "fmt"type T stringtype Node struct {value T
}// Print a node
func (n *Node) Print() string {return fmt.Sprintf("%v", n.value)
}
这里将实现一个无向图,这意味着从A到B添加一条边也会从B到A添加一条边。
func NewGraph() *Graph {g := &Graph{nodes: []*Node{},edges: make(map[Node][]*Node),}return g
}// AddNode adds a node to the graph
func (g *Graph) AddNode(n *Node) {g.Lock()g.nodes = append(g.nodes, n)g.Unlock()
}// AddEdge adds an edge to the graph
func (g *Graph) AddEdge(n1, n2 *Node) {g.Lock()defer g.Unlock()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)
}// Print whole graph
func (g *Graph) Print() {g.Lock()defer g.Unlock()ret := ""for i := 0; i < len(g.nodes); i++ {ret += g.nodes[i].Print() + " -> "neighborhood := g.edges[*g.nodes[i]]for j := 0; j < len(neighborhood); j++ {ret += neighborhood[j].Print() + " "}ret += "\n"}fmt.Println(ret)
}
单元测试
这是一个测试,运行时将填充图结构并打印:
import "testing"var (nA = &Node{"A"}nB = &Node{"B"}nC = &Node{"C"}nD = &Node{"D"}nE = &Node{"E"}nF = &Node{"F"}
)func InitGraph() *Graph {g := NewGraph()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)return g
}func TestGraph_Print(t *testing.T) {g := InitGraph()g.Print()
}
输出:
A -> B C D
B -> A E
C -> A E
D -> A
E -> B C F
F -> E --- PASS: TestGraph_Print (0.00s)
PASS
遍历
BFS(广度优先搜索)是最广为人知的遍历图的算法之一。从一个节点开始,它首先遍历其所有直接链接的节点,然后处理链接到这些节点的节点,依此类推。
它是使用队列实现的,我们可以用之前实现的队列数据结构来辅助完成这个算法:
// Traverse implements the BFS traversing algorithm
func (g *Graph) Traverse(f func(*Node)) {g.RLock()q := NewNodeQueue()n := g.nodes[0]q.Enqueue(n)visited := make(map[*Node]bool)for {if q.IsEmpty() {break}node, _ := q.Dequeue()visited[node] = truenear := 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.RUnlock()
}
我们对算法进行测试:
func TestGraph_Traverse(t *testing.T) {g := InitGraph()g.Traverse(func(n *Node) {fmt.Printf("%v\n", n.value)})
}
输出结果:
A
B
C
D
E
F
--- PASS: TestGraph_Traverse (0.00s)
PASS