Kako implementirati grafično podatkovno strukturo v Golang

Težave, povezane z grafom, se bodo pogosto pojavile v industriji programske opreme. Bodisi v tehničnih razgovorih ali pri izdelavi aplikacij, ki uporabljajo grafe.

Grafi so temeljne podatkovne strukture, ki se uporabljajo v različnih aplikacijah, od družbenih omrežij in transportnih sistemov do mehanizmov za priporočila in analize omrežij.

Kaj je graf in kako lahko implementirate grafe v Go?

Kaj je graf?

Graf je nelinearna podatkovna struktura, ki predstavlja zbirko vozlišč (ali oglišč) in povezav med njimi (robov). Grafi se pogosto uporabljajo v programskih aplikacijah, ki se močno ukvarjajo s povezavami, kot so računalniška omrežja, družbena omrežja in drugo.

Graf je eden od podatkovne strukture, ki bi jih morali poznati kot programer. Grafi zagotavljajo močan in prilagodljiv način za modeliranje in analizo različnih scenarijev iz resničnega sveta, zaradi česar so temeljna in osrednja podatkovna struktura v računalništvu.

Številni algoritmi za reševanje problemov, ki se uporabljajo v svetu programske opreme, temeljijo na grafih. V tem se lahko globlje potopite v grafe vodnik po podatkovni strukturi grafa.

Implementacija grafa v Golangu

Če želite sami implementirati podatkovno strukturo, jo morate večinoma implementirati objektno orientirano programiranje (OOP) pojmov, ampak izvajanje OOP v Go ni popolnoma enak, kot ga imate v drugih jezikih, kot sta Java in C++.

Go uporablja strukture, vrste in vmesnike za implementacijo OOP konceptov in to je vse, kar potrebujete za implementacijo grafične podatkovne strukture in njenih metod.

Graf je sestavljen iz vozlišč (ali oglišč) in robov. Vozlišče je entiteta ali element v grafu. Primer vozlišča je naprava v omrežju ali oseba v družabnem omrežju. Medtem ko je rob povezava ali razmerje med dvema vozliščema.

Če želite implementirati graf v Go, morate najprej definirati strukturo vozlišča, katere lastnost bodo njeni sosedi. Sosedje vozlišča so druga vozlišča, ki so neposredno povezana z vozliščem.

V usmerjenih grafih imajo robovi smeri, tako da se samo vozlišča, na katera kaže dano vozlišče, štejejo za njegove sosede. Medtem ko so v neusmerjenih grafih vsa vozlišča, ki si delijo rob z vozliščem, njegova soseda.

Naslednja koda prikazuje, kako Vozlišče struktura izgleda:

type Node struct {
 Neighbors []*Node
}

V tem članku bo poudarek na neusmerjenem grafu. Za boljšo jasnost pa je tukaj nekaj a Vozlišče struktura za usmerjeni graf je lahko videti takole:

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

S to definicijo je OutNeighbors slice bo shranil vozlišča, do katerih so izhodni robovi iz trenutnega vozlišča, in InNeighbors rezina bo shranila vozlišča, iz katerih prihajajo robovi do trenutnega vozlišča.

Graf boste implementirali z uporabo preslikave celih števil v vozlišča. Ta zemljevid služi kot seznam sosedov (običajni način predstavljanja grafov). Ključ služi kot edinstven ID za vozlišče, vrednost pa bo vozlišče.

Naslednja koda prikazuje Graf struktura:

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

Celoštevilski ključ si lahko predstavljamo tudi kot vrednost vozlišča, v katerega je preslikan. Čeprav je v scenarijih resničnega sveta lahko vaše vozlišče drugačna podatkovna struktura, ki predstavlja profil osebe ali kaj podobnega. V takih primerih bi morali imeti podatke kot eno od lastnosti strukture vozlišča.

Potrebujete funkcijo, ki deluje kot konstruktor za inicializacijo novega grafa. To bo dodelilo pomnilnik za seznam sosednosti in vam omogočilo dodajanje vozlišč v graf. Spodnja koda je definicija konstruktorja za Graf razred:

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

Zdaj lahko definirate metode za izvajanje različnih vrst operacij na grafu. Obstajajo različne operacije, ki jih lahko izvedete na grafu, od dodajanja vozlišč do ustvarjanja robov med vozlišči, iskanja vozlišč in več.

V tem članku boste raziskali funkcije za dodajanje vozlišč in robov grafom ter njihovo odstranjevanje. Naslednje ilustracije kode so implementacije funkcij za izvajanje teh operacij.

Dodajanje vozlišča v graf

Če želite grafu dodati novo vozlišče, potrebujete funkcijo vstavljanja, ki izgleda takole:

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

The AddNode funkcija doda novo vozlišče na graf z ID-jem, ki mu je bil posredovan kot parameter. Funkcija preveri, ali vozlišče z istim ID-jem že obstaja, preden ga doda v graf.

Dodajanje roba grafu

Naslednja pomembna metoda podatkovne strukture grafa je funkcija za dodajanje roba (to je ustvarjanje povezave med dvema vozliščema). Ker je graf tukaj neusmerjen, vam pri ustvarjanju robov ni treba skrbeti za smer.

Tukaj je funkcija za dodajanje roba med dve vozlišči na grafu:

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

Precej preprosto! Dodajanje robov v neusmerjeni graf je preprosto postopek, s katerim oba vozlišča postaneta soseda drug drugemu. Funkcija pridobi obe vozlišči na podlagi ID-jev, ki so ji bili posredovani, in ju obe doda drug drugemu Sosedi rezina.

Odstranjevanje roba iz grafa

Če želite odstraniti vozlišče iz grafa, ga morate odstraniti z vseh seznamov njegovih sosedov, da zagotovite, da ni nedoslednosti podatkov.

Postopek odstranjevanja vozlišča od vseh njegovih sosedov je enak postopku odstranjevanja robov (ali lomljenja povezave) med vozlišči, zato morate najprej definirati funkcijo za odstranjevanje robov, preden definirate tisto, ki odstranite vozlišča.

Spodaj je izvedba removeEdge funkcija:

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

The removeEdge funkcija sprejme dve vozlišči kot parametra in išče indeks drugega (sosednjega) vozlišča na seznamu sosedov glavnega vozlišča. Nato nadaljuje z odstranitvijo soseda vozlišče. Sosedi z uporabo tehnike, imenovane rezanje rezine.

Odstranitev deluje tako, da vzame elemente rezine do podanega indeksa (vendar ne vključuje) in elemente rezine po podanem indeksu ter jih združi. Izpuščanje elementa pri podanem indeksu.

V tem primeru imate neusmerjen graf, zato so njegovi robovi dvosmerni. Zato ste morali poklicati removeEdge dvakrat v glavnem RemoveEdge funkcijo za odstranitev soseda s seznama vozlišča in obratno.

Odstranjevanje vozlišča iz grafa

Ko lahko odstranite robove, lahko odstranite tudi vozlišča. Spodaj je funkcija za odstranjevanje vozlišč iz grafa:

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

Funkcija sprejme ID vozlišča, ki ga morate odstraniti. Preveri, ali vozlišče obstaja, preden nadaljuje z odstranitvijo vseh njegovih robov. Nato izbriše vozlišče iz grafa z uporabo vgrajenega Go-ja izbrisati funkcijo.

Lahko se odločite za implementacijo več metod za svoj graf, kot so funkcije za prečkanje grafa z uporabo iskanja po globini ali iskanja po širini ali funkcijo za tiskanje grafa. Strukturi lahko vedno dodate metode glede na svoje potrebe.

Upoštevati morate tudi, da so grafi zelo učinkoviti, vendar lahko, če se ne uporabljajo pravilno, uničijo strukturo vaše aplikacije. Kot razvijalec morate vedeti, kako izbrati podatkovne strukture za različne primere uporabe.

Zgradite optimizirano programsko opremo z uporabo pravih podatkovnih struktur

Go že ponuja odlično platformo za razvoj učinkovitih programskih aplikacij, ko pa zanemarite dobro razvojne prakse, lahko povzroči različne težave za arhitekturo in delovanje vaše aplikacije.

Ena izmed pomembnih najboljših praks je sprejemanje pravih podatkovnih struktur, kot so nizi, povezani seznami in grafi, za različne potrebe. S tem lahko zagotovite, da vaša aplikacija deluje pravilno, in manj skrbite zaradi ozkih grl ali napak, ki se lahko pojavijo.