Hvordan implementere grafdatastrukturen i Golang

Grafrelaterte problemer vil ofte dukke opp i programvareindustrien. Enten i tekniske intervjuer eller ved bygging av applikasjoner som benytter seg av grafer.

Grafer er grunnleggende datastrukturer som brukes i ulike applikasjoner, alt fra sosiale nettverk og transportsystemer til anbefalingsmotorer og nettverksanalyse.

Hva er en graf, og hvordan kan du implementere grafer i Go?

Hva er en graf?

En graf er en ikke-lineær datastruktur som representerer en samling av noder (eller toppunkter) og forbindelser mellom dem (kanter). Grafer er mye brukt i programmer som håndterer tilkoblinger som datanettverk, sosiale nettverk og mer.

En graf er en av datastrukturene du bør kjenne til som programmerer. Grafer gir en kraftig og fleksibel måte å modellere og analysere ulike scenarier i den virkelige verden på, og dette gjør dem til en grunnleggende og kjernedatastruktur innen informatikk.

Et bredt utvalg av problemløsningsalgoritmer som brukes i programvareverdenen er basert på grafer. Du kan ta et dypere dykk i grafer i denne veiledning til grafdatastrukturen.

Implementering av en graf i Golang

De fleste ganger for å implementere en datastruktur selv, må du implementere objektorientert programmering (OOP) konsepter, men implementere OOP i Go er ikke akkurat det samme som du har det på andre språk som Java og C++.

Go bruker strukturer, typer og grensesnitt for å implementere OOP-konsepter, og disse er alt du trenger for å implementere en grafdatastruktur og dens metoder.

En graf består av noder (eller toppunkter) og kanter. En node er en enhet eller et element i grafen. Et eksempel på en node er en enhet på et nettverk eller en person på et sosialt nettverk. Mens en kant er en forbindelse eller et forhold mellom to noder.

For å implementere en graf i Go, må du først definere en nodestruktur hvis egenskap vil være naboene. Naboene til en node er de andre nodene som er direkte koblet til noden.

I rettet grafer har kanter retninger, så bare nodene som en gitt node peker på, regnes som naboene. Mens i urettede grafer, er alle noder som deler en kant med en node naboene.

Følgende kode viser hvordan Node struktur ser ut:

type Node struct {
 Neighbors []*Node
}

I denne artikkelen vil fokuset være på en urettet graf. Men for å gi bedre klarhet, her er hva en Node struct for en rettet graf kan se slik ut:

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

Med denne definisjonen vil Utenboer slice vil lagre nodene som det er utgående kanter til fra gjeldende node, og I Naboer slice vil lagre nodene som det er innkommende kanter fra til gjeldende node.

Du skal implementere grafen ved å bruke et kart over heltall til noder. Dette kartet fungerer som tilknytningsliste (den vanlige måten å representere grafer på). Nøkkelen fungerer som en unik ID for en node, mens verdien vil være noden.

Følgende kode viser Kurve struktur:

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

Heltallsnøkkelen kan også tenkes som verdien til noden den er tilordnet. Selv om i virkelige scenarier, kan noden din være en annen datastruktur som representerer en persons profil eller noe lignende. I slike tilfeller bør du ha dataene som en av egenskapene til Node-strukturen.

Du trenger en funksjon for å fungere som en konstruktør for initialisering av en ny graf. Dette vil tildele minne for tilstøtningslisten og tillate deg å legge til noder til grafen. Koden nedenfor er definisjonen av en konstruktør for Kurve klasse:

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

Du kan nå definere metoder for å utføre ulike typer operasjoner på grafen. Det er forskjellige operasjoner du kan utføre på en graf, fra å legge til noder til å lage kanter mellom noder, søke etter noder og mer.

I denne artikkelen vil du utforske funksjonene for å legge til noder og kanter til grafer, samt fjerne dem. Følgende kodeillustrasjoner er implementeringer av funksjonene for å utføre disse operasjonene.

Legge til en node i grafen

For å legge til en ny node i grafen trenger du innsettingsfunksjonen som ser slik ut:

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

De AddNode funksjonen legger til en ny node på grafen med ID-en sendt til den som en parameter. Funksjonen sjekker om en node med samme ID allerede eksisterer før den legges til i grafen.

Legge til en kant til grafen

Den neste viktige metoden for grafdatastrukturen er funksjonen for å legge til en kant (det vil si å lage en forbindelse mellom to noder). Siden grafen her er urettet, er det ingen grunn til å bekymre seg for retning når du lager kanter.

Her er funksjonen for å legge til en kant mellom to noder på grafen:

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

Ganske enkelt! Tilføyelsen av kanter i en urettet graf er ganske enkelt prosessen med å gjøre begge nodene til naboer av hverandre. Funksjonen får begge nodene av ID-ene som sendes til den og legger begge til hverandres Naboer skive.

Fjerne en kant fra grafen

For å fjerne en node fra en graf, må du fjerne den fra alle nabolistene for å sikre at det ikke er datainkonsekvenser.

Prosessen med å fjerne en node fra alle naboene er den samme som prosessen med å fjerne kanter (eller bryte forbindelser) mellom nodene, derfor må du definere funksjonen for å fjerne kanter først før du definerer den som skal fjerne noder.

Nedenfor er implementeringen av fjerne Edge funksjon:

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

De fjerne Edge funksjonen aksepterer to noder som parametere og søker etter den andre (nabo-)nodens indeks i hovednodens naboliste. Det går så videre å fjerne naboen fra node. Naboer ved hjelp av en teknikk kalt kutte skiven.

Fjerningen fungerer ved å ta elementene i skiven opp til (men ikke inkludere) den spesifiserte indeksen, og elementer i skiven fra etter den spesifiserte indeksen, og sette dem sammen. Utelater elementet ved den angitte indeksen.

I dette tilfellet har du en urettet graf, derfor er kantene toveis. Dette er grunnen til at du måtte ringe fjerne Edge to ganger i hovedsak Fjern Edge funksjon for å fjerne naboen fra nodens liste og omvendt.

Fjerne en node fra grafen

Når du er i stand til å fjerne kanter, kan du også fjerne noder. Nedenfor er funksjonen for å fjerne noder fra grafen:

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

Funksjonen godtar ID-en til noden du må fjerne. Den sjekker om noden eksisterer før den fortsetter å fjerne alle kantene. Den sletter deretter noden fra grafen ved å bruke Gos innebygde slette funksjon.

Du kan velge å implementere flere metoder for grafen din, for eksempel funksjoner for å krysse grafen ved å bruke avd-først-søk eller bredde-først-søk, eller en funksjon for å skrive ut grafen. Du kan alltid legge til metoder til strukturen i henhold til dine behov.

Du bør også merke deg at grafer er svært effektive, men hvis de ikke brukes riktig, kan de ødelegge applikasjonsstrukturen. Du må vite hvordan du velger datastrukturer for ulike brukstilfeller som utvikler.

Bygg optimalisert programvare ved å bruke de riktige datastrukturene

Go gir allerede en flott plattform for å utvikle effektive programvareapplikasjoner, men når du forsømmer godt utviklingspraksis, kan det forårsake forskjellige problemer for applikasjonens arkitektur og ytelse.

En viktig beste praksis er å ta i bruk de riktige datastrukturene som arrays, koblede lister og grafer, for ulike behov. Med dette kan du sikre at applikasjonen din fungerer som den skal og bekymre deg mindre om ytelsesflaskehalser eller feil som kan oppstå.