วิธีการใช้โครงสร้างข้อมูลกราฟใน Golang

การนำทางความท้าทายเกี่ยวกับกราฟเป็นสิ่งที่เกิดขึ้นทั่วไปภายในขอบเขตของการพัฒนาซอฟต์แวร์ ไม่ว่าจะเป็นช่วงสัมภาษณ์ด้านเทคนิคหรือในขณะที่สร้างแอปพลิเคชันที่รวมโครงสร้างกราฟ

ทฤษฎีกราฟเป็นสาขาหนึ่งของคณิตศาสตร์ที่เกี่ยวข้องกับการศึกษากราฟ ซึ่งเป็นโครงสร้างข้อมูลพื้นฐานที่ใช้ในแอปพลิเคชันที่หลากหลาย เช่น แพลตฟอร์มเครือข่ายสังคม โครงสร้างพื้นฐานด้านการขนส่ง อัลกอริทึมคำแนะนำ และการวิเคราะห์เครือข่าย

ในขอบเขตของวิทยาการคอมพิวเตอร์ กราฟหมายถึงโครงสร้างข้อมูลที่ประกอบด้วยโหนดที่เชื่อมต่อกันด้วยขอบ โหนดเป็นตัวแทนของแต่ละองค์ประกอบหรือเอนทิตี ในขณะที่ขอบแสดงถึงความสัมพันธ์ระหว่างกัน จุดประสงค์ของการนำกราฟไปใช้คือเพื่อสร้างแบบจำลองระบบที่ซับซ้อนด้วยส่วนประกอบที่เชื่อมต่อกัน ซึ่งอำนวยความสะดวกในการแก้ปัญหาผ่านอัลกอริทึมต่างๆ เช่น การค้นหาเชิงลึกก่อน การค้นหาแนวกว้าง อัลกอริทึมของ Dijkstra และอื่นๆ ในภาษาโปรแกรม Go เราอาจใช้แพ็คเกจเช่น “github.com/gonum/graph” เพื่อการนำแนวคิดทฤษฎีกราฟไปใช้อย่างมีประสิทธิภาพ

กราฟคืออะไร?

กราฟสามารถกำหนดได้ว่าเป็นระบบที่ซับซ้อนซึ่งประกอบด้วยองค์ประกอบที่เชื่อมต่อถึงกัน ซึ่งเรียกว่าโหนดหรือจุดยอด ซึ่งเชื่อมต่อกันด้วยขอบที่แสดงถึงความสัมพันธ์หรือการเชื่อมโยง โครงสร้างข้อมูลนี้มีความโดดเด่นในโดเมนต่างๆ ซึ่งการเชื่อมต่อมีบทบาทสำคัญ เช่น เครือข่ายคอมพิวเตอร์ เครือข่ายสังคมออนไลน์ และแอปพลิเคชันอื่นๆ อีกมากมาย

ในฐานะโปรแกรมเมอร์ที่มีความเชี่ยวชาญ จำเป็นอย่างยิ่งที่คุณจะต้องทำความคุ้นเคยกับกราฟ ซึ่งเป็นโครงสร้างข้อมูลสำคัญที่นำเสนอวิธีการที่กว้างขวางและปรับเปลี่ยนได้ในการแสดงและตรวจสอบสถานการณ์ในชีวิตจริงที่หลากหลาย กราฟเป็นองค์ประกอบที่ขาดไม่ได้ของวิทยาการคอมพิวเตอร์ ทำหน้าที่เป็นรากฐานที่สำคัญสำหรับแอปพลิเคชันจำนวนมาก และถูกนำไปใช้อย่างแพร่หลายในอุตสาหกรรมต่างๆ เนื่องจากความเก่งกาจและประสิทธิภาพที่ไม่มีใครเทียบได้

สำรวจความซับซ้อนของเทคนิคการแก้ปัญหาโดยใช้กราฟที่แพร่หลายในแวดวงของการเขียนโปรแกรมคอมพิวเตอร์โดยเจาะลึกทรัพยากรที่ครอบคลุมของเราที่ให้การตรวจสอบเชิงลึกของโครงสร้างข้อมูลกราฟ นำเสนอข้อมูลเชิงลึกและการใช้งานจริงสำหรับผู้ที่ต้องการเพิ่มพูนความเข้าใจเกี่ยวกับ แนวคิดที่สำคัญนี้

การใช้กราฟใน Golang

เพื่อสร้างโครงสร้างข้อมูลตั้งแต่ต้น โดยทั่วไปจะใช้หลักการเขียนโปรแกรมเชิงวัตถุ อย่างไรก็ตาม ในขณะที่การเขียนโปรแกรมเชิงวัตถุเป็นส่วนสำคัญของการพัฒนาภาษา Go การนำไปใช้นั้นแตกต่างอย่างมากจากที่พบในภาษาต่างๆ เช่น Java และ C++

การใช้โครงสร้าง ประเภท และอินเทอร์เฟซ Go นำเสนอการนำหลักการเขียนโปรแกรมเชิงวัตถุมาใช้ ซึ่งช่วยให้สามารถสร้างโครงสร้างข้อมูลกราฟและการดำเนินการที่เกี่ยวข้องผ่านการใช้โครงสร้าง ประเภท และอินเทอร์เฟซเพียงอย่างเดียว

ในทฤษฎีกราฟ กราฟประกอบด้วยโหนดหรือจุดยอด ซึ่งแสดงถึงเอนทิตีหรือองค์ประกอบภายในโครงสร้างกราฟิก ตัวอย่างเช่น โหนดอาจหมายถึงอุปกรณ์ที่เชื่อมต่อกับเครือข่ายหรือบุคคลที่เข้าร่วมในแพลตฟอร์มโซเชียลมีเดีย ในทางกลับกัน ขอบหมายถึงความสัมพันธ์หรือความเชื่อมโยงที่เชื่อมโยงสองโหนดเข้าด้วยกัน โดยพื้นฐานแล้ว กราฟจะแสดงให้เห็นถึงความเชื่อมโยงระหว่างส่วนประกอบต่างๆ ผ่านการเชื่อมต่อหรือความสัมพันธ์เหล่านี้

ในการสร้างกราฟโดยใช้ภาษาโปรแกรม Go เริ่มแรกจำเป็นต้องสร้างโครงสร้างโหนดที่มีคุณสมบัติสะท้อนโหนดที่อยู่ติดกัน โหนดข้างเคียงเหล่านี้เป็นตัวแทนของโหนดที่เชื่อมต่อโดยตรงกับโหนดที่ระบุ

ในกราฟกำกับ ขอบมีการวางแนวที่เฉพาะโหนดที่โหนดใดโหนดหนึ่งมุ่งตรงไปเท่านั้นที่ถือว่าเป็นเพื่อนบ้าน ในทางกลับกัน ในกราฟที่ไม่มีการกำหนดทิศทาง โหนดทั้งหมดที่เข้าร่วมในขอบที่ใช้ร่วมกันกับโหนดหนึ่งๆ จะรับรู้เป็นโหนดข้างเคียง

รหัสที่กำหนดแสดงภาพประกอบของโครงสร้างและลักษณะของวัตถุโหนดอย่างครบถ้วน แสดงคุณลักษณะต่างๆ และค่าที่สอดคล้องกัน

 type Node struct {
    Neighbors []*Node
}

เพื่ออธิบายแนวคิดของกราฟที่ไม่มีการกำหนดทิศทาง เราจะอธิบายลักษณะเฉพาะโดยละเอียด เพื่อความชัดเจน ให้เรานำเสนอตัวอย่างโครงสร้างโหนดสำหรับกราฟโดยตรงที่แสดงให้เห็นถึงโครงสร้างและการจัดระเบียบ

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

ด้วยการใช้เส้นแบ่งนี้ OutNeighborsarray จะรักษารายการของโหนดที่มีขอบกำกับภายนอกที่มาจากโหนดปัจจุบัน ในขณะที่ส่วนประกอบ InNeighbors จะเก็บชุดของโหนดที่ให้ขอบขาเข้าไปยังโหนดปัจจุบัน

ในการสร้างกราฟ เราจะใช้ตัวอย่างของโครงสร้างข้อมูลที่เรียกว่าแผนที่ ซึ่งแต่ละรายการประกอบด้วยคีย์จำนวนเต็มและค่าโหนดที่เกี่ยวข้อง การกำหนดค่านี้เรียกโดยทั่วไปว่าการแสดงรายการคำเชื่อม ซึ่งคีย์ทำหน้าที่เป็นตัวระบุเฉพาะสำหรับโหนดแต่ละโหนด ในขณะที่ค่าที่เกี่ยวข้องกำหนดโหนดเดียวกันเหล่านั้นภายในกราฟ

รหัสต่อไปนี้แสดงโครงสร้างกราฟ:

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

แนวคิดของคีย์จำนวนเต็มสามารถคิดได้เทียบเท่ากับค่าที่เกี่ยวข้องกับโหนดที่เกี่ยวข้อง อย่างไรก็ตาม ในสถานการณ์จริง การแสดงโหนดอาจไม่จำกัดเฉพาะจำนวนเต็มอย่างง่ายเสมอไป โหนดอาจแสดงโครงสร้างข้อมูลที่ซับซ้อนมากขึ้นแทน เช่น โปรไฟล์สำหรับบุคคลหรือเอนทิตีอื่นๆ ที่คล้ายคลึงกัน ในกรณีเหล่านี้ จะเป็นการเหมาะสมที่จะรวมข้อมูลที่เกี่ยวข้องภายในโครงสร้างโหนดเองโดยการรวมเป็นหนึ่งในคุณสมบัติ

โค้ดที่ให้มาแสดงถึงเมธอดคอนสตรัคเตอร์สำหรับคลาส กราฟ ซึ่งทำหน้าที่เริ่มต้นอินสแตนซ์ใหม่ของโครงสร้างข้อมูลกราฟโดยจัดสรรหน่วยความจำสำหรับการแสดงรายการคำเชื่อมและอนุญาตให้เพิ่มโหนดในกราฟ

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

เพื่ออำนวยความสะดวกในการจัดการกับโครงสร้างข้อมูลกราฟ เราสามารถใช้ชุดของวิธีการที่เปิดใช้งานการดำเนินการของฟังก์ชันที่หลากหลาย เช่น การแทรกโหนด การสร้างขอบ ความสามารถในการค้นหา และงานอื่น ๆ ที่เกี่ยวข้อง ช่วงของการดำเนินการที่สามารถดำเนินการบนกราฟนั้นกว้างขวาง ครอบคลุมการรวมโหนดใหม่ การสร้างการเชื่อมต่อระหว่างโหนดที่มีอยู่ การดึงองค์ประกอบเฉพาะ และความเป็นไปได้เพิ่มเติมมากมาย

ในข้อความนี้ เราจะเจาะลึกถึงความสามารถในการจัดการกราฟผ่านการใช้งานฟังก์ชันที่เปิดใช้งานการเพิ่มและลบทั้งโหนดและขอบภายในกราฟ ตัวอย่างรหัสที่ตามมาเป็นตัวอย่างของการใช้งานจริงของการดำเนินการดังกล่าว

การเพิ่มโหนดในกราฟ

ในการรวมองค์ประกอบใหม่เข้ากับกราฟ ต้องใช้การดำเนินการแทรกซึ่งแสดงสูตรต่อไปนี้:

 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!")
    }
}

ฟังก์ชัน"AddNode"ออกแบบมาเพื่อรวมองค์ประกอบใหม่ภายในกราฟ และทำได้โดยยอมรับตัวระบุ ซึ่งทำหน้าที่เป็นข้อมูลอ้างอิงเฉพาะสำหรับส่วนประกอบดังกล่าว เป็นพารามิเตอร์อินพุต อย่างไรก็ตาม ก่อนที่จะรวมส่วนเพิ่มเติมที่เสนอใหม่นี้เข้ากับเครือข่าย ระบบจะตรวจสอบว่าเอนทิตีอื่นได้รับการกำหนดตำแหน่งที่เหมือนกันก่อนหน้านี้หรือไม่ เพื่อป้องกันการซ้ำซ้อนหรือความซ้ำซ้อนภายในโครงสร้างของกราฟ

การเพิ่มขอบให้กับกราฟ

เพื่อสร้างการเชื่อมต่อระหว่างสองโหนดในโครงสร้างข้อมูลกราฟแบบไม่มีทิศทาง เราใช้ฟังก์ชัน EdgeInsertion ซึ่งเพิ่มขอบ เนื่องจากกราฟไม่มีการเชื่อมต่อโดยตรง จึงไม่ต้องกังวลเกี่ยวกับการวางแนวในขณะที่สร้างลิงก์

โค้ดที่ให้มาใช้วิธีเพิ่มขอบกำกับระหว่างจุดยอดสองจุดในกราฟถ่วงน้ำหนัก โดยอิงจากระยะทางแบบยุคลิดที่คำนวณโดยใช้ฟังก์ชัน Distance และน้ำหนักของขอบที่จัดเก็บไว้ในเมทริกซ์คำเชื่อม ขอบใหม่ถูกเพิ่มเข้าไปในชุดเพื่อนบ้านของจุดยอดต้นทางและเป้าหมาย ซึ่งเป็นอาร์เรย์ที่มีจุดยอดทั้งหมดที่เชื่อมต่อผ่านเมทริกซ์ที่อยู่ติดกัน

 func (g *Graph) AddEdge(nodeID1, nodeID2 int) {
    node1 := g.nodes[nodeID1]
    node2 := g.nodes[nodeID2]

    node1.Neighbors = append(node1.Neighbors, node2)
    node2.Neighbors = append(node2.Neighbors, node1)
}

ในกราฟที่ไม่มีทิศทาง การเพิ่มขอบเกี่ยวข้องกับการกำหนดโหนดสองโหนดให้เป็นเพื่อนบ้านซึ่งกันและกัน ซึ่งสามารถทำได้ผ่านขั้นตอนที่ตรงไปตรงมา โดยใช้ตัวระบุโหนดที่กำหนดเพื่อผนวกทั้งสองโหนดเข้ากับรายการองค์ประกอบข้างเคียงตามลำดับของกันและกัน

การลบขอบออกจากกราฟ

ในการกำจัดจุดยอดออกจากกราฟในขณะที่รักษาความสมบูรณ์ของข้อมูลที่แสดงโดยกราฟดังกล่าว จำเป็นต้องลบจุดยอดนั้นออกจากรายการของโหนดข้างเคียงแต่ละรายการ สิ่งนี้ทำให้มั่นใจได้ว่าข้อมูลที่แสดงโดยกราฟจะไม่มีความคลาดเคลื่อน

ในการลบโหนดเฉพาะออกจากโหนดที่อยู่ติดกันแต่ละโหนด จำเป็นต้องสร้างวิธีการสำหรับกำจัดความสัมพันธ์ระหว่างโหนดในขั้นต้น ดังนั้น ก่อนที่จะกำหนดอัลกอริทึมสำหรับกำจัดโหนดแต่ละโหนด จำเป็นต้องมีการกำหนดวิธีการที่เป็นระบบสำหรับการตัดความสัมพันธ์ที่ผูกโหนดเหล่านี้เข้าด้วยกัน

ข้อมูลโค้ดที่ให้ไว้แสดงวิธีการลบขอบออกจากกราฟ ซึ่งแสดงเป็น removeEdge(edge) ภายในคลาสกราฟ การใช้งานเกี่ยวข้องกับการวนซ้ำผ่านแต่ละโหนดในรายการโหนดและตรวจสอบว่าตรงกับหนึ่งในจุดสิ้นสุดของขอบที่ระบุหรือไม่ หากพบ โหนดทั้งสองจะถูกลบออกจากรายการโหนดตามลำดับ ต่อจากนั้น ข้อมูลของ Edge และการอ้างอิงถึงสองโหนดจะถูกลบด้วย

 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")
}

ฟังก์ชัน removeEdge รับสองโหนดเป็นอินพุตและค้นหาดัชนีของโหนดที่สองภายในรายการเพื่อนบ้านของโหนดแรก ต่อจากนั้น จะใช้วิธีที่เรียกว่า"การหั่นเป็นชิ้น"เพื่อกำจัดการเชื่อมต่อระหว่างกัน

กระบวนการเกี่ยวข้องกับการแยกองค์ประกอบภายในช่วงที่กำหนด ยกเว้นองค์ประกอบที่ดัชนีที่ระบุ จากนั้นจึงรวมองค์ประกอบเหล่านั้นเข้ากับองค์ประกอบที่เป็นไปตามดัชนีดังกล่าวอย่างราบรื่น ดังนั้น องค์ประกอบที่อยู่ในตำแหน่งที่กำหนดจึงถูกข้ามไป

ในสถานการณ์ที่มีกราฟที่ไม่มีทิศทางแสดงอยู่ กราฟนี้มีขอบแบบสองทิศทาง ทำให้ต้องใช้เมธอด removeEdge สองครั้งภายในฟังก์ชัน RemoveEdge หลักเพื่อลบเพื่อนบ้านทั้งสองออกจากรายการโหนดที่เกี่ยวข้อง

การลบโหนดออกจากกราฟ

เมื่อกำจัดขอบภายในกราฟได้สำเร็จ ก็จะสามารถกำจัดแต่ละโหนดได้เช่นกัน ต่อไปนี้แสดงถึงฟังก์ชันที่อำนวยความสะดวกในการลบโหนดออกจากกราฟ:

 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")
}

ฟังก์ชันที่มีให้ใช้เป็นอินพุตของตัวระบุเฉพาะที่สอดคล้องกับโหนดเฉพาะภายในกราฟ และตรวจสอบว่ามีโหนดดังกล่าวอยู่ภายในโครงสร้างข้อมูลพื้นฐานหรือไม่ หากสามารถพบโหนดที่ระบุได้ ฟังก์ชันจะดำเนินการตัดการเชื่อมต่อจากขอบทุกด้านที่เชื่อมต่อกับโหนดนั้น หลังจากนั้นจะลบโหนดออกทั้งหมดโดยใช้กลไกการลบในตัวซึ่งมีอยู่ในภาษาการเขียนโปรแกรมของ Go

คุณมีตัวเลือกในการรวมเทคนิคเพิ่มเติมสำหรับการสำรวจกราฟ รวมถึงอัลกอริทึมการค้นหาเชิงลึกและการค้นหาแนวกว้าง นอกเหนือจากวิธีการแสดงกราฟ การใช้ฟังก์ชันเหล่านี้มีความยืดหยุ่นและปรับเปลี่ยนได้ตามความต้องการของคุณ

ในฐานะนักพัฒนา สิ่งสำคัญคือต้องคำนึงถึงประสิทธิภาพและประสิทธิผลของโครงสร้างข้อมูลกราฟในการจัดการกับข้อกำหนดกรณีการใช้งานเฉพาะ การใช้โครงสร้างเหล่านี้อย่างไม่เหมาะสมอาจนำไปสู่ผลเสียต่อสถาปัตยกรรมโดยรวมของแอปพลิเคชัน ดังนั้นจึงจำเป็นอย่างยิ่งที่จะต้องมีความเข้าใจอย่างรอบด้านในการเลือกโครงสร้างข้อมูลที่เหมาะสมตามความต้องการเฉพาะของแต่ละสถานการณ์

สร้างซอฟต์แวร์ที่ปรับให้เหมาะสมโดยใช้โครงสร้างข้อมูลที่เหมาะสม

Go เป็นรากฐานที่ยอดเยี่ยมในการสร้างโซลูชันซอฟต์แวร์ที่มีประสิทธิภาพสูง อย่างไรก็ตาม การไม่คำนึงถึงวิธีการเขียนโปรแกรมเสียงอาจทำให้เกิดความยุ่งยากเกี่ยวกับโครงสร้างและประสิทธิภาพของแอปพลิเคชันได้

การใช้โครงสร้างข้อมูลที่เหมาะสม รวมถึงอาร์เรย์ รายการที่เชื่อมโยง และกราฟ เป็นแนวทางปฏิบัติที่ดีที่สุดที่สำคัญเพื่อให้แน่ใจว่าแอปพลิเคชันทำงานได้อย่างเหมาะสมที่สุด ในขณะเดียวกันก็ลดปัญหาที่อาจเกิดขึ้นซึ่งเกี่ยวข้องกับปัญหาคอขวดของประสิทธิภาพหรือความล้มเหลวของระบบ