Kuidas rakendada Golangis graafiku andmestruktuuri

Graafikuga seotud probleemid ilmnevad sageli tarkvaratööstuses. Kas tehnilistes intervjuudes või graafikuid kasutavate rakenduste loomisel.

Graafikud on põhilised andmestruktuurid, mida kasutatakse erinevates rakendustes, alates sotsiaalvõrgustikest ja transpordisüsteemidest kuni soovitusmootorite ja võrguanalüüsini.

Mis on graafik ja kuidas saate graafikuid Go-s rakendada?

Mis on graafik?

Graaf on mittelineaarne andmestruktuur, mis kujutab sõlmede (või tippude) ja nendevaheliste ühenduste (servade) kogumit. Graafikuid kasutatakse laialdaselt tarkvararakendustes, mis tegelevad tugevalt selliste ühendustega nagu arvutivõrgud, sotsiaalvõrgustikud ja palju muud.

Graafik on üks andmestruktuurid, mida peaksite teadma programmeerijana. Graafikud pakuvad võimsat ja paindlikku viisi erinevate reaalsete stsenaariumide modelleerimiseks ja analüüsimiseks ning see muudab need arvutiteaduse põhi- ja põhiandmestruktuuriks.

Graafidel põhinevad paljud tarkvaramaailmas kasutatavad probleemide lahendamise algoritmid. Selles saate graafikutesse sügavamalt sukelduda graafiku andmestruktuuri juhend.

Graafiku rakendamine Golangis

Enamasti tuleb andmestruktuuri ise juurutamiseks rakendada objektorienteeritud programmeerimine (OOP) mõisted, kuid OOP-i rakendamine Go-s ei ole täpselt sama, mis teil on teistes keeltes, nagu Java ja C++.

Go kasutab OOP-kontseptsioonide rakendamiseks struktuure, tüüpe ja liideseid ning need on kõik, mida vajate graafiku andmestruktuuri ja selle meetodite rakendamiseks.

Graaf koosneb sõlmedest (või tippudest) ja servadest. Sõlm on üksus või element graafikus. Sõlme näiteks on seade võrgus või inimene sotsiaalvõrgustikus. Kuigi serv on ühendus või suhe kahe sõlme vahel.

Graafi rakendamiseks Go-s peate esmalt määratlema sõlmestruktuuri, mille omadused on selle naabrid. Sõlme naabrid on teised sõlmed, mis on sõlmega vahetult ühendatud.

Suunatud graafides on servadel suunad, nii et selle naabriteks loetakse ainult neid sõlmi, millele antud sõlm osutab. Suunamata graafikute puhul on kõik sõlmed, millel on sõlmega serv, selle naabrid.

Järgmine kood näitab, kuidas Sõlm struktuur näeb välja:

type Node struct {
 Neighbors []*Node
}

Selles artiklis keskendutakse suunamata graafikule. Parema selguse huvides on siin aga toodud a Sõlm Suunatud graafiku struktuur võib välja näha järgmine:

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

Selle määratlusega Välisnaabrid slice salvestab sõlmed, milleni on praegusest sõlmest väljuvad servad, ja In Naabrid slice salvestab sõlmed, millest praegusesse sõlme sisenevad servad.

Rakendate graafiku täisarvude ja sõlmede kaardi abil. See kaart toimib kui naabrusnimekiri (tavaline graafikute esitamise viis). Võti toimib sõlme kordumatu ID-na, väärtus on aga sõlm.

Järgmine kood näitab Graafik struktuur:

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

Täisarvu võtit võib ette kujutada ka selle sõlme väärtusena, millega see on vastendatud. Kuigi reaalse maailma stsenaariumide korral võib teie sõlm olla erinev andmestruktuur, mis esindab inimese profiili või midagi sarnast. Sellistel juhtudel peaksid andmed olema sõlmestruktuuri üks omadusi.

Teil on vaja funktsiooni, mis toimiks uue graafiku lähtestamiseks konstruktorina. See eraldab naaberkohtade loendi jaoks mälu ja võimaldab teil lisada graafikule sõlmi. Allolev kood on konstruktori määratlus Graafik klass:

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

Nüüd saate määratleda meetodid mitmesuguste toimingute tegemiseks graafikul. Graafikul on võimalik teha erinevaid toiminguid alates sõlmede lisamisest kuni sõlmedevaheliste servade loomiseni, sõlmede otsimiseni ja palju muud.

Selles artiklis uurite graafikutele sõlmede ja servade lisamise ning nende eemaldamise funktsioone. Järgmised koodi illustratsioonid on nende toimingute teostamise funktsioonide teostused.

Sõlme lisamine graafikule

Graafikule uue sõlme lisamiseks vajate sisestusfunktsiooni, mis näeb välja järgmine:

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 funktsioon lisab graafikule uue sõlme, millele on parameetrina edastatud ID. Funktsioon kontrollib enne graafikule lisamist, kas sama ID-ga sõlm on juba olemas.

Graafikule serva lisamine

Graafiku andmestruktuuri järgmine oluline meetod on serva lisamise funktsioon (st kahe sõlme vahelise ühenduse loomine). Kuna siinne graafik on suunamata, ei pea servi luues suuna pärast muretsema.

Siin on funktsioon serva lisamiseks graafiku kahe sõlme vahele:

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

Päris lihtne! Servade liitmine suunamata graafis on lihtsalt protsess, mille käigus mõlemad sõlmed muutuvad üksteise naabriteks. Funktsioon hangib mõlemad sõlmed talle edastatud ID-de järgi ja lisab need mõlemad üksteise sõlmedesse Naabrid viil.

Graafikult serva eemaldamine

Sõlme graafikult eemaldamiseks peate selle eemaldama kõigist selle naabrite loenditest, et tagada andmete vastuolude puudumine.

Sõlme eemaldamine kõigist selle naabritest on sama, mis servade eemaldamine (või purunemine ühendused) sõlmede vahel, seega peate esmalt määratlema servade eemaldamise funktsiooni, enne kui määrate eemaldage sõlmed.

Allpool on toodud selle rakendamine eemalda Edge funktsioon:

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 eemalda Edge funktsioon aktsepteerib kahte sõlme parameetritena ja otsib teise (naaber)sõlme indeksi põhisõlme naabrite loendist. Seejärel eemaldatakse naaber sõlm. Naabrid kasutades tehnikat nn viilu viilutamine.

Eemaldamine toimub nii, et viilu elemendid viiakse kuni määratud indeksini (kuid mitte kaasa arvatud) ja lõigu elemendid pärast määratud indeksit ning need ühendatakse. Määratud indeksiga elemendi väljajätmine.

Sel juhul on teil suunamata graaf, seetõttu on selle servad kahesuunalised. Sellepärast pidite helistama eemalda Edge kaks korda põhiliselt Eemalda Edge funktsioon naabri eemaldamiseks sõlme loendist ja vastupidi.

Sõlme eemaldamine graafikult

Kui saate servad eemaldada, saate eemaldada ka sõlmed. Allpool on funktsioon sõlmede eemaldamiseks graafikult:

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

Funktsioon aktsepteerib eemaldatava sõlme ID-d. Enne kõigi selle servade eemaldamist kontrollib see, kas sõlm on olemas. Seejärel kustutab see sõlme graafikult, kasutades Go sisseehitatud funktsiooni kustutada funktsiooni.

Võite valida graafiku jaoks rohkemate meetodite rakendamise, näiteks funktsioonid graafiku läbimiseks, kasutades osakonnaotsingut või laiuseotsingut, või funktsiooni graafiku printimiseks. Struktuurile saab alati lisada meetodeid vastavalt oma vajadustele.

Samuti peaksite arvestama, et graafikud on väga tõhusad, kuid kui neid õigesti ei kasutata, võivad need teie rakenduse struktuuri rikkuda. Peate arendajana teadma, kuidas valida andmestruktuure erinevateks kasutusjuhtudeks.

Looge optimeeritud tarkvara õigete andmestruktuuride abil

Go juba pakub suurepärast platvormi tõhusate tarkvararakenduste arendamiseks, kuid kui jätate hea tähelepanuta arendustavad, võib see põhjustada teie rakenduse arhitektuuri ja jõudluse jaoks erinevaid probleeme.

Üks oluline hea tava on erinevate vajaduste jaoks õigete andmestruktuuride (nt massiivid, lingitud loendid ja graafikud) kasutuselevõtt. Selle abil saate tagada, et teie rakendus töötab õigesti ja muretsete vähem jõudluse kitsaskohtade või tõrgete pärast.