نحوه پیاده سازی ساختار داده نمودار در Golang

نمودارها یکی از ضروری ترین ساختارهای داده ای هستند که به عنوان یک برنامه نویس باید آن را بشناسید. نحوه پیاده سازی آن در Golang را بیاموزید.

مشکلات مربوط به نمودار اغلب در صنعت نرم افزار به سراغ شما می آیند. چه در مصاحبه های فنی و چه هنگام ساخت برنامه هایی که از نمودارها استفاده می کنند.

نمودارها ساختارهای داده بنیادی هستند که در برنامه های مختلف، از شبکه های اجتماعی و سیستم های حمل و نقل گرفته تا موتورهای توصیه و تحلیل شبکه مورد استفاده قرار می گیرند.

گراف چیست و چگونه می توان نمودارها را در Go پیاده سازی کرد؟

نمودار چیست؟

گراف یک ساختار داده غیر خطی است که مجموعه ای از گره ها (یا رئوس) و اتصالات بین آنها (لبه ها) را نشان می دهد. نمودارها به طور گسترده در برنامه های نرم افزاری استفاده می شوند که به شدت با اتصالاتی مانند شبکه های کامپیوتری، شبکه های اجتماعی و غیره سروکار دارند.

گراف یکی از ساختارهای داده ای است که به عنوان یک برنامه نویس باید آن را بشناسید. نمودارها روشی قدرتمند و انعطاف‌پذیر برای مدل‌سازی و تجزیه و تحلیل سناریوهای مختلف دنیای واقعی ارائه می‌کنند و این باعث می‌شود که آنها به ساختار داده‌ای بنیادی و هسته‌ای در علوم کامپیوتر تبدیل شوند.

طیف گسترده ای از الگوریتم های حل مسئله مورد استفاده در دنیای نرم افزار بر اساس نمودارها هستند. شما می توانید در این راهنمای ساختار داده گراف، عمیق تر به نمودارها بپردازید.

پیاده سازی نمودار در Golang

اغلب اوقات برای پیاده سازی یک ساختار داده توسط خودتان، باید مفاهیم برنامه نویسی شی گرا (OOP) را پیاده سازی کنید، اما پیاده سازی OOP در Go دقیقاً مشابه آن در زبان های دیگر مانند Java و C++ نیست.

Go از ساختارها، انواع و رابط‌ها برای پیاده‌سازی مفاهیم OOP استفاده می‌کند و اینها تمام چیزی است که برای پیاده‌سازی ساختار داده گراف و روش‌های آن نیاز دارید.

یک نمودار از گره ها (یا رئوس) و یال ها تشکیل شده است. گره یک موجودیت یا عنصر در گراف است. نمونه ای از گره، دستگاهی در شبکه یا شخصی در شبکه اجتماعی است. در حالی که لبه یک اتصال یا رابطه بین دو گره است.

برای پیاده سازی یک گراف در Go، ابتدا باید یک ساختار گره را تعریف کنید که ویژگی آن همسایه های آن باشد. همسایه های یک گره، گره های دیگری هستند که مستقیماً به گره متصل هستند.

در نمودارهای جهت دار، یال ها دارای جهت هستند، بنابراین تنها گره هایی که یک گره معین به آنها اشاره می کند، همسایه آن در نظر گرفته می شوند. در حالی که در گراف های بدون جهت، تمام گره هایی که یک یال مشترک با یک گره دارند، همسایه آن هستند.

کد زیر نشان می دهد که ساختار Node چگونه به نظر می رسد:

type Node struct {
    Neighbors []*Node
}

در این مقاله، تمرکز بر روی یک گراف بدون جهت خواهد بود. با این حال، برای ارائه وضوح بهتر، در اینجا یک ساختار Node برای یک گراف جهت دار ممکن است شبیه باشد:

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

با این تعریف، برش OutNeighbors گره هایی را که لبه های خروجی از گره فعلی به آنها وجود دارد، و برش InNeighbors گره هایی را که از آنها لبه های ورودی به گره فعلی وجود دارد، ذخیره می کند.

شما نمودار را با استفاده از نقشه ای از اعداد صحیح به گره ها پیاده سازی خواهید کرد. این نقشه به عنوان لیست مجاورت (روش رایج نمایش نمودارها) عمل می کند. کلید به عنوان یک شناسه منحصر به فرد برای یک گره عمل می کند، در حالی که مقدار آن گره خواهد بود.

کد زیر ساختار Graph را نشان می دهد:

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

کلید عدد صحیح را می توان به عنوان مقدار گره ای که به آن نگاشت می شود نیز تصور کرد. اگرچه در سناریوهای دنیای واقعی، گره شما می تواند یک ساختار داده متفاوت باشد که نمایه یک شخص یا چیزی مشابه را نشان می دهد. در چنین مواردی، باید داده ها را به عنوان یکی از ویژگی های ساختار Node داشته باشید.

شما به یک تابع نیاز دارید تا به عنوان سازنده برای مقداردهی اولیه یک گراف جدید عمل کند. این کار حافظه را برای لیست مجاورت اختصاص می دهد و به شما امکان می دهد گره ها را به نمودار اضافه کنید. کد زیر تعریف سازنده کلاس Graph است:

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 یک گره جدید روی گراف اضافه می کند که شناسه به عنوان پارامتر به آن ارسال شده است. این تابع قبل از اضافه کردن گره به گراف بررسی می کند که آیا گره ای با همان شناسه قبلاً وجود دارد یا خیر.

اضافه کردن لبه به نمودار

روش مهم بعدی ساختار داده گراف، تابع افزودن یک یال (یعنی ایجاد ارتباط بین دو گره) است. از آنجایی که نمودار در اینجا یک گراف بدون جهت است، نیازی به نگرانی در مورد جهت هنگام ایجاد لبه ها نیست.

در اینجا تابع اضافه کردن یک یال بین دو گره در نمودار است:

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

خیلی ساده! افزودن یال ها در یک گراف بدون جهت صرفاً فرآیند همسایه کردن هر دو گره با یکدیگر است. این تابع هر دو گره را توسط شناسه‌هایی که به آن ارسال می‌شود دریافت می‌کند و هر دوی آنها را به تکه Neighbors یکدیگر اضافه می‌کند.

حذف یک لبه از نمودار

برای حذف یک گره از یک گراف، باید آن را از لیست همسایگانش حذف کنید تا اطمینان حاصل کنید که هیچ تناقضی در داده ها وجود ندارد.

فرآیند حذف یک گره از همه همسایه هایش مانند فرآیند حذف لبه ها (یا قطع اتصالات) بین گره ها است، از این رو باید ابتدا قبل از تعریف یکی برای حذف گره ها، تابع حذف یال ها را تعریف کنید.

در زیر اجرای تابع 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")
}

تابع 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، گره را از نمودار حذف می کند.

می‌توانید روش‌های بیشتری را برای نمودار خود پیاده‌سازی کنید، مانند توابعی برای عبور از نمودار با استفاده از جستجوی dept-first یا width-first search یا تابعی برای چاپ نمودار. شما همیشه می توانید بر اساس نیاز خود متدهایی را به ساختار اضافه کنید.

همچنین باید توجه داشته باشید که نمودارها بسیار کارآمد هستند، اما اگر به درستی استفاده نشوند، می توانند ساختار برنامه شما را خراب کنند. شما باید بدانید که چگونه ساختارهای داده را برای موارد استفاده مختلف به عنوان یک توسعه دهنده انتخاب کنید.

ایجاد نرم افزار بهینه با استفاده از ساختارهای داده مناسب

Go در حال حاضر یک پلتفرم عالی برای توسعه برنامه‌های کاربردی نرم‌افزاری کارآمد ارائه می‌دهد، اما وقتی از شیوه‌های توسعه خوب غفلت می‌کنید، می‌تواند مشکلات مختلفی را برای معماری و عملکرد برنامه شما ایجاد کند.

یکی از بهترین روش‌های مهم، اتخاذ ساختارهای داده مناسب مانند آرایه‌ها، فهرست‌های پیوندی و نمودارها برای نیازهای مختلف است. با این کار، می‌توانید اطمینان حاصل کنید که برنامه شما به درستی کار می‌کند و کمتر نگران گلوگاه‌های عملکرد یا شکست‌هایی که ممکن است پیش بیاید، باشید.

منبع مقاله