Đi cấu trúc dữ liệu: Đồ thị

Phân tích và triển khai cấu trúc dữ liệu Đồ thị trong Go

Ađồ thịlà một đại diện của một cấu trúc mạng. Có rất nhiều ví dụ về biểu đồ trong thế giới thực, Internet và biểu đồ xã hội là những ví dụ cổ điển.

Về cơ bản nó là một tập hợp củađiểm giaokết nối bởicác cạnh.

Tôi sẽ bỏ qua các khái niệm toán học vì bạn có thể tìm thấy chúng ở khắp mọi nơi và chuyển trực tiếp đến phần triển khai Go của biểu đồ.

Thực hiện

Cấu trúc dữ liệu biểu đồ sẽ hiển thị các phương pháp đó:

  • AddNode()chèn một nút
  • AddEdge()thêm một cạnh giữa hai nút

String()cho mục đích kiểm tra.

Biểu đồ được định nghĩa là

type ItemGraph struct {
    nodes []*Node
    edges map[Node][]*Node
    lock  sync.RWMutex
}

với Node là

type Node struct {
    value Item
}

Tôi sẽ triển khai một đồ thị vô hướng, có nghĩa là thêm một cạnh từ A đến B cũng sẽ thêm một cạnh từ B đến A.

Thực hiện

// Package graph creates a ItemGraph data structure for the Item type
package graph

import ( “fmt” “sync”

<span style="color:#e6db74">"github.com/cheekybits/genny/generic"</span>

)

// Item the type of the binary search tree type Item generic.Type

// Node a single node that composes the tree type Node struct { value Item }

func (n *Node) String() string { return fmt.Sprintf("%v", n.value) }

// ItemGraph the Items graph type ItemGraph struct { nodes []Node edges map[Node][]Node lock sync.RWMutex }

// AddNode adds a node to the graph func (g ItemGraph) AddNode(n Node) { g.lock.Lock() g.nodes = append(g.nodes, n) g.lock.Unlock() }

// AddEdge adds an edge to the graph func (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 graph func (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() }

Khá đơn giản. Đây là một thử nghiệm mà khi chạy, sẽ điền vào biểu đồ và in

$ go test
A -> B C D
B -> A E
C -> A E
D -> A
E -> B C F
F -> E

PASS

package graph

import ( “fmt” “testing” )

var g ItemGraph

func 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)

<span style="color:#a6e22e">g</span>.<span style="color:#a6e22e">AddEdge</span>(<span style="color:#f92672">&amp;</span><span style="color:#a6e22e">nA</span>, <span style="color:#f92672">&amp;</span><span style="color:#a6e22e">nB</span>)
<span style="color:#a6e22e">g</span>.<span style="color:#a6e22e">AddEdge</span>(<span style="color:#f92672">&amp;</span><span style="color:#a6e22e">nA</span>, <span style="color:#f92672">&amp;</span><span style="color:#a6e22e">nC</span>)
<span style="color:#a6e22e">g</span>.<span style="color:#a6e22e">AddEdge</span>(<span style="color:#f92672">&amp;</span><span style="color:#a6e22e">nB</span>, <span style="color:#f92672">&amp;</span><span style="color:#a6e22e">nE</span>)
<span style="color:#a6e22e">g</span>.<span style="color:#a6e22e">AddEdge</span>(<span style="color:#f92672">&amp;</span><span style="color:#a6e22e">nC</span>, <span style="color:#f92672">&amp;</span><span style="color:#a6e22e">nE</span>)
<span style="color:#a6e22e">g</span>.<span style="color:#a6e22e">AddEdge</span>(<span style="color:#f92672">&amp;</span><span style="color:#a6e22e">nE</span>, <span style="color:#f92672">&amp;</span><span style="color:#a6e22e">nF</span>)
<span style="color:#a6e22e">g</span>.<span style="color:#a6e22e">AddEdge</span>(<span style="color:#f92672">&amp;</span><span style="color:#a6e22e">nD</span>, <span style="color:#f92672">&amp;</span><span style="color:#a6e22e">nA</span>)

}

func TestAdd(t *testing.T) { fillGraph() g.String() }

Duyệt qua biểu đồ: BFS

BFS(Breadth-First Search) là một trong những thuật toán được biết đến rộng rãi nhất để duyệt qua một biểu đồ. Bắt đầu từ một nút, đầu tiên nó đi qua tất cả các nút được liên kết trực tiếp của nó, sau đó xử lý các nút được liên kết với các nút đó, v.v.

Nó được triển khai bằng cách sử dụng một hàng đợi, được tạo từBắt đầu triển khai cấu trúc dữ liệu hàng đợivới tạo mã cho loại nút:

// This file was automatically generated by genny.
// Any changes will be lost if this file is regenerated.
// see https://github.com/cheekybits/genny
package graph

import “sync”

// NodeQueue the queue of Nodes type NodeQueue struct { items []Node lock sync.RWMutex }

// New creates a new NodeQueue func (s NodeQueue) New() NodeQueue { s.lock.Lock() s.items = []Node{} s.lock.Unlock() return s }

// Enqueue adds an Node to the end of the queue func (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 queue func (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 it func (s NodeQueue) Front() Node { s.lock.RLock() item := s.items[0] s.lock.RUnlock() return &item }

// IsEmpty returns true if the queue is empty func (s *NodeQueue) IsEmpty() bool { s.lock.RLock() defer s.lock.RUnlock() return len(s.items) == 0 }

// Size returns the number of Nodes in the queue func (s *NodeQueue) Size() int { s.lock.RLock() defer s.lock.RUnlock() return len(s.items) }

Phương pháp traverse

Đây là cách triển khai BFS:

// Traverse implements the BFS traversing algorithm
func (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]
    <span style="color:#66d9ef">for</span> <span style="color:#a6e22e">i</span> <span style="color:#f92672">:=</span> <span style="color:#ae81ff">0</span>; <span style="color:#a6e22e">i</span> &lt; len(<span style="color:#a6e22e">near</span>); <span style="color:#a6e22e">i</span><span style="color:#f92672">++</span> {
        <span style="color:#a6e22e">j</span> <span style="color:#f92672">:=</span> <span style="color:#a6e22e">near</span>[<span style="color:#a6e22e">i</span>]
        <span style="color:#66d9ef">if</span> !<span style="color:#a6e22e">visited</span>[<span style="color:#a6e22e">j</span>] {
            <span style="color:#a6e22e">q</span>.<span style="color:#a6e22e">Enqueue</span>(<span style="color:#f92672">*</span><span style="color:#a6e22e">j</span>)
            <span style="color:#a6e22e">visited</span>[<span style="color:#a6e22e">j</span>] = <span style="color:#66d9ef">true</span>
        }
    }
    <span style="color:#66d9ef">if</span> <span style="color:#a6e22e">f</span> <span style="color:#f92672">!=</span> <span style="color:#66d9ef">nil</span> {
        <span style="color:#a6e22e">f</span>(<span style="color:#a6e22e">node</span>)
    }
}
<span style="color:#a6e22e">g</span>.<span style="color:#a6e22e">lock</span>.<span style="color:#a6e22e">RUnlock</span>()

}

có thể được kiểm tra với

func TestTraverse(t *testing.T) {
    g.Traverse(func(n *Node) {
        fmt.Printf("%v\n", n)
    })
}

mà sau khi được thêm vào các thử nghiệm của chúng tôi, sẽ in ra con đường cần thiết để đi qua tất cả các nút của chúng tôi:

A
B
C
D
A
E
F

Tạo cấu trúc dữ liệu biểu đồ cụ thể

Bạn có thể sử dụng cách áp dụng chung này để tạo các biểu đồ loại cụ thể, bằng cách sử dụng

//generate a `IntGraph` graph of `int` values
genny -in graph.go -out graph-int.go gen "Item=int"

//generate a </span>StringGraph<span style="color:#e6db74"> graph of </span>string<span style="color:#e6db74"> values genny -in graph.go -out graph-string.go gen “Item=string”


Các hướng dẫn về go khác: