Cách triển khai cấu trúc dữ liệu biểu đồ trong Golang

Biểu đồ là một trong số cấu trúc dữ liệu cần thiết mà bạn phải biết khi là một lập trình viên. Hãy cùng nhau học cách tạo cấu trúc dữ liệu đồ thị/biểu đồ trong Golang nhé!

Những vấn đề liên quan tới biểu đồ thường có trong lĩnh vực công nghệ phần mềm, từ phỏng vấn về kỹ thuật tới xây dựng ứng dụng dùng đồ thị.

Biểu đồ là cấu trúc dữ liệu cơ bản được dùng ở các ứng dụng khác nhau, từ mạng xã hội, hệ thống giao thông tới công cụ đề xuất và phân tích mạng.

Vậy biểu đồ là gì? Cách bạn có thể triển khai biểu đồ trong Go như thế nào?

Đồ thị, biểu đồ là gì?

Đồ thị là một cấu trúc dữ liệu phi tuyến tính, đại diện cho một bộ sưu tập node (hoặc đỉnh) và kết nối giữa chúng (cạnh). Biểu đồ được sử dụng rộng rãi trong ứng dụng phần mềm “nặng” về kết nối như mạng máy tính, mạng xã hội và nhiều hơn thế nữa.

Biểu đồ là một trong số cấu trúc dữ liệu mà bạn nên biết khi là lập trình viên. Biểu đồ mang tới một cách mạnh mẽ & linh hoạt để tạo mẫu, đồng thời, phân tích đa dạng các cảnh thế giới thực và khiến chúng trở thành một cấu trúc dữ liệu cốt lõi & cơ bản trong khoa học máy tính.

Một loạt thuật toán giải quyết vấn đề hiện nay được dùng trong thế giới phần mềm dựa trên biểu đồ/đồ thị.

Triển khai biểu đồ trong Golang

Khi tự triển khai một cấu trúc dữ liệu, gần nhưu bạn đều cần triển khai các khái niệm lập trình hướng đối tượng (OOP), nhưng tạo OOP trong Go không giống như vậy vì bạn có nó trong ngôn ngữ khác như Java và C++.

Go dùng cấu trúc (struct), kiểu (type) và giao diện (interface) để triển khai những khái niệm OOP. Chúng là tất cả những thứ bạn cần để tạo một cấu trúc dữ liệu biểu đồ cùng phương thức của nó.

Một biểu đồ chứa các node (hoặc đỉnh) & cạnh. Node là một thực thể hoặc thành phần trong biểu đồ. Ví dụ, node là một thiết bị trên mạng hoặc một người trên mạng xã hội, còn edge là một kết nối hoặc mối quan hệ giữa hai node.

Để triển khai một đồ thị trong Go, đầu tiên, bạn cần xác định một cấu trúc node sở hữu thuộc tính là neighbor của nó. Neighbor của node là các node khác mà trực tiếp được kết nối với node đó.

Code sau minh họa cách cấu trúc Node:

type Node struct {
    Neighbors []*Node
}

Trọng tâm hướng dẫn sẽ vào biểu đồ vô hướng. Tuy nhiên, để rõ ràng hoan, đây là một cấu trúc Node dành cho biểu đồ có hướng:

type Node struct {
    OutNeighbors []*Node // outgoing edges
    InNeighbors []*Node // incoming edges
}

Với định nghĩa này, slice OutNeighbors sẽ chứa các node với cạnh đi ra từ node hiện tại, còn slice InNeighbors sẽ chứa node mà các cạnh đi đến node hiện tại.

Bạn sẽ triển khai một đồ thị bằng cách dùng bản đồ các số nguyên dẫn tới node. Bản đồ này hoạt động giống như adjacency list. Chìa khóa đóng vai trò là ID duy nhất cho node, còn giá trị sẽ là node.

Code sau sẽ hiện cấu trúc Graph:

type Graph struct {
    nodes map[int]*Node
}

Key số nguyên cũng có thể được hình dung như giá trị của node mà nó được ánh xạ tới. Dù trong những bối cảnh thực tế, node của bạn có thể là một cấu trúc dữ liệu khác, đại diện cho hồ sơ của một cá nhân hay điều gì đó tương tự. Trong những trường hợp như thế, bạn nên có dữ liệu là một trong số thuộc tính của cấu trúc Node.

Bạn cần một hàm hoạt động như hàm tạo đồ thị mới. Điều này sẽ phân bổ bộ nhớ cho danh sách liền kề, đồng thời, cho phép bạn thêm node vào biểu đồ. Code bên dưới định nghĩa hàm tạo cho class Graph:

func NewGraph() *Graph {
    return &Graph{
        nodes: make(map[int]*Node),
    }
}

Giờ bạn có thể xác định các phương thức triển khai nhiều hoạt động khác nhau trên đồ thị, từ bổ sung node tới tạo edge giữa các node, tìm node…

Thêm node vào biểu đồ

Bạn cần hàm chèn như sau:

func (g *Graph) AddNode(nodeID int) {
    if _, exists := g.nodes[nodeID]; !exists {
        newNode := &Node{
            Neighbors: []*Node{},
        }
        g.nodes[nodeID] = newNode
        fmt.Println("New node added to graph")
    } else {
        fmt.Println("Node already exists!")
    }
}

Hàm AddNode thêm một node mới vào biểu đồ với ID đã chuyển sang nó dưới dạng tham số. Hàm này kiểm tra xem liệu một node có cùng ID đã tồn tại trước khi thêm nó vào biểu đồ hay chưa.

Thêm edge vào biểu đồ

Phương thức quan trọng tiếp theo của cấu trúc dữ liệu biểu đồ là hàm thêm edge. Vì biểu đồ này là vô hướng, bạn không cần lo về hướng khi tạo edge.

Đây là hàm thêm edge giữa hai node trên biểu đồ:

func (g *Graph) AddNode(nodeID int) {
    if _, exists := g.nodes[nodeID]; !exists {
        newNode := &Node{
            Neighbors: []*Node{},
        }
        g.nodes[nodeID] = newNode
        fmt.Println("New node added to graph")
    } else {
        fmt.Println("Node already exists!")
    }
}

Việc bổ sung edge trong biểu đồ vô hướng chỉ đơn giản là quá trình tạo cả hai node liền kề nhau. Hàm này nhận cả hai node bằng ID đã chuyển sang nó và nối cả hai vào slice Neighbors của nhau.

Loại bỏ edge khỏi biểu đồ

Để loại bỏ một node khỏi biểu đồ, bạn cần xóa nó khỏi tất cả danh sách neighbor liên quan để đảm bảo không tồn tại sự thiếu nhất quán về dữ liệu.

Quá trình xóa node từ tất cả neighbor giống như quá trình loại bỏ edge (hoặc ngắt kết nối) giữa các node, vì thế, bạn phải xác định hàm xóa edge đầu tiên, trước khi xác định chức năng loại bỏ node.

Dưới đây là triển khai hàm removeEdge:

func (g *Graph) removeEdge(node, neighbor *Node) {
    index := -1
    for i, n := range node.Neighbors {
        if n == neighbor {
            index = i
            break
        }
    }
    if index != -1 {
        node.Neighbors = 
            append(node.Neighbors[:index], node.Neighbors[index+1:]...)
    }
}

func (g *Graph) RemoveEdge(node, neighbor *Node) {
    g.removeEdge(node, neighbor)
    g.removeEdge(neighbor, node)
    fmt.Println("Edge successfully removed")
}

Hàm removeEdge chấp nhận hai node là tham số và tìm index của node thứ hai trong danh sách neighbor của node chính. Sau đó, nó tiếp tục loại bỏ neighbor từ node.Neighbors bằng kỹ thuật tên slicing the slice.

Việc loại bỏ hoạt động bằng cách lấy các phần tử của lát cắt (nhưng không bao gồm) cho tới chỉ mục cụ thể, các thành phần của slice từ sau index đã chỉ định và nối chúng. Để lại chỉ mục phần tử đã xác định.

Trong trường hợp này, bạn có một biểu đồ vô hướng, vì thế edge của nó là hai chiều. Đây là lí do tại sao bạn phải gọi removeEdge hai lần trong hàm RemoveEdge chính để loại bỏ neighbor từ danh sách của node và ngược lại.

Loại bỏ một node khỏi biểu đồ

Dưới đây là hàm loại bỏ node khỏi biểu đồ:

func (g *Graph) RemoveNode(nodeID int) {
    node, exists := g.nodes[nodeID]
    if !exists {
        fmt.Println("Node doesn't exist")
        return
    }

    for _, neighbor := range node.Neighbors {
        g.RemoveEdge(node, neighbor)
    }
    delete(g.nodes, nodeID)
    fmt.Println("Node deleted successfully")
}

Hàm này chấp nhận ID của node bạn cần loại bỏ. Nó kiểm tra xem node có tồn tại hay không trước khi tiếp tục loại bỏ tất cả các cạnh của nó. Sau đó, nó sẽ xóa node khỏi biểu đồ bằng chức năng delete sẵn có trong Go.

Trên đây là cách tạo cấu trúc dữ liệu biểu đồ trong Go. Hi vọng bài viết hữu ích với các bạn.