Sådan implementeres grafdatastrukturen i Golang

Graf-relaterede problemer vil ofte komme din vej i softwareindustrien. Uanset om det er i tekniske interviews eller ved opbygning af applikationer, der gør brug af grafer.

Grafer er grundlæggende datastrukturer, der bruges i forskellige applikationer, lige fra sociale netværk og transportsystemer til anbefalingsmotorer og netværksanalyse.

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

Hvad er en graf?

En graf er en ikke-lineær datastruktur, der repræsenterer en samling af noder (eller knudepunkter) og forbindelser mellem dem (kanter). Grafer er meget brugt i softwareapplikationer, der beskæftiger sig meget med forbindelser som computernetværk, sociale netværk og mere.

En graf er en af de datastrukturer, du bør kende som programmør. Grafer giver en kraftfuld og fleksibel måde at modellere og analysere forskellige scenarier i den virkelige verden på, og dette gør dem til en grundlæggende og kernedatastruktur inden for datalogi.

En lang række problemløsningsalgoritmer, der bruges i softwareverdenen, er baseret på grafer. Du kan tage et dybere dyk ned i grafer i denne guide til grafens datastruktur.

Implementering af en graf i Golang

De fleste gange skal du implementere en datastruktur for dig selv objektorienteret programmering (OOP) begreber, men implementering af OOP i Go er ikke helt det samme, som du har det på andre sprog som Java og C++.

Go bruger strukturer, typer og grænseflader til at implementere OOP-koncepter, og disse er alt hvad du behøver for at implementere en grafdatastruktur og dens metoder.

En graf består af knudepunkter (eller knudepunkter) og kanter. En node er en enhed eller et element i grafen. Et eksempel på en node er en enhed på et netværk eller en person på et socialt netværk. Mens en kant er en forbindelse eller et forhold mellem to noder.

For at implementere en graf i Go skal du først definere en nodestruktur, hvis egenskab vil være dens naboer. Naboerne til en node er de andre noder, der er direkte forbundet til noden.

I rettede grafer har kanter retninger, så kun de noder, som en given node peger på, betragtes som dens naboer. Mens der er i urettede grafer, er alle noder, der deler en kant med en node, dens naboer.

Følgende kode viser, hvordan Node struktur ser ud:

type Node struct {
 Neighbors []*Node
}

I denne artikel vil fokus være på en urettet graf. Men for at give bedre klarhed er her, hvad en Node struct for en rettet graf kan se sådan ud:

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

Med denne definition er Udenboer slice vil gemme de noder, hvortil der er udgående kanter fra den aktuelle node, og I Naboer slice vil gemme de noder, hvorfra der er indgående kanter til den aktuelle node.

Du implementerer grafen ved hjælp af et kort over heltal til noder. Dette kort fungerer som tilknytningsliste (den almindelige måde at repræsentere grafer på). Nøglen fungerer som et unikt ID for en node, mens værdien vil være noden.

Følgende kode viser Kurve struktur:

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

Heltalsnøglen kan også forestilles som værdien af ​​den node, den er knyttet til. Selvom i virkelige scenarier, kan din node være en anden datastruktur, der repræsenterer en persons profil eller noget lignende. I sådanne tilfælde bør du have dataene som en af ​​egenskaberne for Node-strukturen.

Du skal bruge en funktion til at fungere som konstruktør til initialisering af en ny graf. Dette vil allokere hukommelse til nabolisten og give dig mulighed for at tilføje noder til grafen. Koden nedenfor er definitionen af ​​en konstruktør for Kurve klasse:

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

Du kan nu definere metoder til at udføre forskellige slags operationer på grafen. Der er forskellige handlinger, som du kan udføre på en graf, lige fra tilføjelse af noder til oprettelse af kanter mellem noder, søgning efter noder og mere.

I denne artikel vil du udforske funktionerne til at tilføje noder og kanter til grafer samt fjerne dem. De følgende kodeillustrationer er implementeringerne af funktionerne til at udføre disse operationer.

Tilføjelse af en node til grafen

For at tilføje en ny node til grafen skal du bruge indsættelsesfunktionen, der ser sådan ud:

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

Det TilføjNode funktionen tilføjer en ny node på grafen med ID'et videregivet til det som en parameter. Funktionen kontrollerer, om en node med samme ID allerede eksisterer, før den tilføjes til grafen.

Tilføjelse af en kant til grafen

Den næste vigtige metode til grafdatastrukturen er funktionen til at tilføje en kant (det vil sige at skabe en forbindelse mellem to noder). Da grafen her er urettet, er der ingen grund til at bekymre sig om retning, når du opretter kanter.

Her er funktionen til at tilføje en kant mellem 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)
}

Ret simpelt! Tilføjelsen af ​​kanter i en urettet graf er simpelthen processen med at gøre begge noder til naboer af hinanden. Funktionen får begge noder af de ID'er, der sendes til den og føjer dem begge til hinandens Naboer skive.

Fjernelse af en kant fra grafen

For at fjerne en node fra en graf, skal du fjerne den fra alle dens nabolister for at sikre, at der ikke er datainkonsekvenser.

Processen med at fjerne en node fra alle dens naboer er den samme som processen med at fjerne kanter (eller bryde forbindelser) mellem noderne, derfor skal du først definere funktionen til fjernelse af kanter, før du definerer den til fjerne noder.

Nedenfor er implementeringen af fjerne Kanten fungere:

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

Det fjerne Kanten funktionen accepterer to noder som parametre og søger efter den anden (nabo) nodes indeks i hovedknudens naboliste. Det går så videre med at fjerne naboen fra node. Naboer ved hjælp af en teknik kaldet skære skiven.

Fjernelsen fungerer ved at tage elementerne i udsnittet op til (men ikke inkludere) det angivne indeks, og elementer af udsnittet fra efter det angivne indeks, og sammenkæde dem. Udelader elementet ved det angivne indeks.

I dette tilfælde har du en urettet graf, derfor er dens kanter tovejs. Det er derfor, du skulle ringe til fjerne Kanten to gange i hovedsagen Fjern Edge funktion til at fjerne naboen fra nodens liste og omvendt.

Fjernelse af en node fra grafen

Når du er i stand til at fjerne kanter, kan du også fjerne noder. Nedenfor er funktionen til at 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")
}

Funktionen accepterer ID'et for den node, som du skal fjerne. Den kontrollerer, om noden eksisterer, før den fortsætter med at fjerne alle dens kanter. Det sletter derefter noden fra grafen ved hjælp af Go's indbyggede slette fungere.

Du kan vælge at implementere flere metoder til din graf, såsom funktioner til at krydse grafen ved at bruge afd-først søgning eller bredde-først søgning, eller en funktion til at udskrive grafen. Du kan altid tilføje metoder til strukturen efter dine behov.

Du skal også bemærke, at grafer er meget effektive, men hvis de ikke bruges korrekt, kan de ødelægge din applikationsstruktur. Du skal vide, hvordan du vælger datastrukturer til forskellige use cases som udvikler.

Byg optimeret software ved hjælp af de rigtige datastrukturer

Go giver allerede en fantastisk platform til at udvikle effektive softwareapplikationer, men når du forsømmer godt udviklingspraksis, kan det forårsage forskellige problemer for din applikations arkitektur og ydeevne.

En vigtig bedste praksis er at anvende de rigtige datastrukturer såsom arrays, sammenkædede lister og grafer til forskellige behov. Med dette kan du sikre dig, at din applikation fungerer korrekt og bekymre dig mindre om ydeevneflaskehalse eller fejl, der kan opstå.