Golang'da Grafik Veri Yapısı Nasıl Uygulanır?

Grafikle ilgili sorunlar genellikle yazılım endüstrisinde karşınıza çıkacaktır. Teknik görüşmelerde veya grafiklerden yararlanan uygulamalar oluştururken.

Grafikler, sosyal ağlar ve ulaşım sistemlerinden öneri motorlarına ve ağ analizine kadar çeşitli uygulamalarda kullanılan temel veri yapılarıdır.

Grafik nedir ve Go'da grafikleri nasıl uygulayabilirsiniz?

Grafik Nedir?

Bir grafik, bir düğümler (veya köşeler) koleksiyonunu ve bunlar arasındaki bağlantıları (kenarlar) temsil eden doğrusal olmayan bir veri yapısıdır. Grafikler, bilgisayar ağları, sosyal ağlar ve daha fazlası gibi bağlantılarla yoğun bir şekilde ilgilenen yazılım uygulamalarında yaygın olarak kullanılır.

Bir grafik, bilmeniz gereken veri yapıları bir programcı olarak. Grafikler, çeşitli gerçek dünya senaryolarını modellemek ve analiz etmek için güçlü ve esnek bir yol sağlar ve bu, onları bilgisayar biliminde temel ve temel bir veri yapısı yapar.

Yazılım dünyasında kullanılan çok çeşitli problem çözme algoritmaları grafiklere dayalıdır. Bu konuda grafiklere daha derin bir dalış yapabilirsiniz. grafik veri yapısı kılavuzu.

Golang'da Grafik Uygulamak

Çoğu zaman bir veri yapısını kendiniz uygulamak için uygulamanız gerekir. nesne yönelimli programlama (OOP) kavramlar ama Go'da OOP uygulamak Java ve C++ gibi diğer dillerde sahip olduğunuzla tam olarak aynı değildir.

Go, OOP kavramlarını uygulamak için yapıları, türleri ve arabirimleri kullanır ve bunlar, bir grafik veri yapısını ve yöntemlerini uygulamak için ihtiyacınız olan tek şeydir.

Bir grafik, düğümlerden (veya tepe noktalarından) ve kenarlardan oluşur. Düğüm, grafikteki bir varlık veya öğedir. Bir düğüm örneği, bir ağdaki bir cihaz veya bir sosyal ağdaki bir kişidir. Bir kenar, iki düğüm arasındaki bir bağlantı veya ilişki iken.

Go'da bir grafik uygulamak için, önce özelliği komşuları olacak bir düğüm yapısı tanımlamanız gerekir. Bir düğümün komşuları, düğüme doğrudan bağlı olan diğer düğümlerdir.

Yönlü grafiklerde, kenarların yönleri vardır, bu nedenle yalnızca belirli bir düğümün işaret ettiği düğümler komşuları olarak kabul edilir. Yönsüz grafiklerde, bir düğümle bir kenarı paylaşan tüm düğümler onun komşularıdır.

Aşağıdaki kod, düğüm yapı görünüyor:

type Node struct {
 Neighbors []*Node
}

Bu yazıda, yönsüz bir graf üzerinde durulacaktır. Ancak, daha iyi netlik sağlamak için, burada düğüm yönlendirilmiş bir grafik için yapı şöyle görünebilir:

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

Bu tanımla, Komşular dilim, geçerli düğümden giden kenarların olduğu düğümleri saklar ve Komşularda dilim, geçerli düğüme gelen kenarların olduğu düğümleri saklar.

Grafiği, tam sayıların düğümlere eşlemesini kullanarak uygulayacaksınız. Bu harita, bitişik liste (grafikleri temsil etmenin yaygın yolu). Anahtar, bir düğüm için benzersiz bir kimlik görevi görürken, değer düğüm olacaktır.

Aşağıdaki kod gösterir grafik yapı:

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

Tamsayı anahtarı, eşlendiği düğümün değeri olarak da düşünülebilir. Gerçek dünya senaryolarında, düğümünüz bir kişinin profilini veya benzer bir şeyi temsil eden farklı bir veri yapısı olabilir. Bu gibi durumlarda, verilere Node yapısının özelliklerinden biri olarak sahip olmalısınız.

Yeni bir grafiği başlatmak için yapıcı görevi görecek bir işleve ihtiyacınız var. Bu, bitişiklik listesi için bellek ayıracak ve grafiğe düğümler eklemenize izin verecektir. Aşağıdaki kod, için bir yapıcının tanımıdır. grafik sınıf:

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

Artık grafik üzerinde çeşitli türde işlemleri gerçekleştirmek için yöntemler tanımlayabilirsiniz. Düğümlerin eklenmesinden düğümler arasında kenarların oluşturulmasına, düğümlerin aranmasına ve daha fazlasına kadar bir grafik üzerinde gerçekleştirebileceğiniz çeşitli işlemler vardır.

Bu makalede, grafiklere düğüm ve kenar ekleme ve bunları kaldırma işlevlerini keşfedeceksiniz. Aşağıdaki kod çizimleri, bu işlemleri gerçekleştirmeye yönelik işlevlerin uygulamalarıdır.

Grafiğe Düğüm Ekleme

Grafiğe yeni bir düğüm eklemek için şuna benzeyen ekleme işlevine ihtiyacınız vardır:

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

bu Düğüm ekle işlevi, kendisine parametre olarak iletilen kimlikle grafiğe yeni bir düğüm ekler. İşlev, grafiğe eklemeden önce aynı kimliğe sahip bir düğümün var olup olmadığını kontrol eder.

Grafiğe Kenar Ekleme

Grafik veri yapısının bir sonraki önemli yöntemi, bir kenar ekleme (yani, iki düğüm arasında bir bağlantı oluşturma) işlevidir. Buradaki grafik yönsüz olduğundan, kenarları oluştururken yön konusunda endişelenmenize gerek yoktur.

Grafikteki iki düğüm arasına bir kenar ekleme işlevi şöyledir:

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

Gayet basit! Yönsüz bir grafta kenarların eklenmesi, basitçe her iki düğümü birbirine komşu yapma işlemidir. İşlev, kendisine iletilen kimliklerle her iki düğümü de alır ve her ikisini de birbirinin sonuna ekler. komşular dilim.

Grafikten Kenar Kaldırma

Bir düğümü bir grafikten kaldırmak için, veri tutarsızlıkları olmadığından emin olmak için düğümü tüm komşularının listelerinden çıkarmanız gerekir.

Bir düğümü tüm komşularından çıkarma işlemi, kenarları kaldırma (veya kırma) işlemiyle aynıdır. bağlantılar) düğümler arasında, bu nedenle, birini tanımlamadan önce kenarları kaldırma işlevini tanımlamanız gerekir. düğümleri kaldır

Aşağıda, uygulamanın KaldırKenar işlev:

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

bu KaldırKenar işlev, iki düğümü parametre olarak kabul eder ve ana düğümün komşular listesinde ikinci (komşu) düğümün dizinini arar. Daha sonra komşuyu çıkarmak için devam eder. düğüm. komşular adı verilen bir teknik kullanarak dilimi dilimlemek.

Kaldırma işlemi, dilimin öğelerini belirtilen dizine kadar alarak (ancak dahil etmeyerek) ve dilimin öğelerini belirtilen dizinden sonra alarak ve bunları birleştirerek çalışır. Öğeyi belirtilen dizinde bırakmak.

Bu durumda, yönsüz bir grafiğiniz var, bu nedenle kenarları çift yönlüdür. Bu yüzden aramak zorunda kaldınız. KaldırKenar iki kez ana Kenarı Kaldır komşuyu düğüm listesinden çıkarma işlevi ve bunun tersi de geçerlidir.

Grafikten Düğüm Çıkarma

Kenarları kaldırabildiğinizde, düğümleri de kaldırabilirsiniz. Aşağıda, grafikten düğümleri kaldırma işlevi verilmiştir:

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

İşlev, kaldırmanız gereken düğümün kimliğini kabul eder. Tüm kenarlarını kaldırmaya devam etmeden önce düğümün var olup olmadığını kontrol eder. Daha sonra, Go'nun yerleşik özelliğini kullanarak düğümü grafikten siler. silmek işlev.

Grafiğiniz için derinlik öncelikli arama veya genişlik öncelikli aramayı kullanarak grafiği çaprazlamak için işlevler veya grafiği yazdırmak için bir işlev gibi daha fazla yöntem uygulamayı seçebilirsiniz. Yapıya her zaman ihtiyaçlarınıza göre yöntemler ekleyebilirsiniz.

Ayrıca grafiklerin çok verimli olduğunu ancak doğru kullanılmadığı takdirde uygulama yapınızı bozabileceğini de unutmamalısınız. Bir geliştirici olarak farklı kullanım durumları için veri yapılarını nasıl seçeceğinizi bilmelisiniz.

Doğru Veri Yapılarını Kullanarak Optimize Edilmiş Yazılımlar Oluşturun

Go zaten verimli yazılım uygulamaları geliştirmek için harika bir platform sağlıyor, ancak iyiyi ihmal ettiğinizde geliştirme uygulamaları, uygulamanızın mimarisi ve performansı için farklı sorunlara neden olabilir.

Önemli bir en iyi uygulama, farklı ihtiyaçlar için diziler, bağlantılı listeler ve grafikler gibi doğru veri yapılarını benimsemektir. Bununla, uygulamanızın doğru çalıştığından emin olabilir ve ortaya çıkabilecek performans darboğazları veya arızaları hakkında daha az endişe duyabilirsiniz.