Hoe de grafiekgegevensstructuur in Golang te implementeren

Grafiekgerelateerde problemen komen vaak op je pad in de software-industrie. Of het nu gaat om technische interviews of het bouwen van applicaties die gebruik maken van grafieken.

Grafieken zijn fundamentele gegevensstructuren die in verschillende toepassingen worden gebruikt, variërend van sociale netwerken en transportsystemen tot aanbevelingsengines en netwerkanalyse.

Wat is een grafiek en hoe kun je grafieken implementeren in Go?

Wat is een grafiek?

Een grafiek is een niet-lineaire gegevensstructuur die een verzameling knooppunten (of hoekpunten) en verbindingen daartussen (randen) vertegenwoordigt. Grafieken worden veel gebruikt in softwaretoepassingen die veel te maken hebben met verbindingen zoals computernetwerken, sociale netwerken en meer.

Een grafiek is er een van de gegevensstructuren die u moet kennen als programmeur. Grafieken bieden een krachtige en flexibele manier om verschillende real-world scenario's te modelleren en te analyseren, en dit maakt ze tot een fundamentele en kerngegevensstructuur in de informatica.

Een grote verscheidenheid aan probleemoplossende algoritmen die in de softwarewereld worden gebruikt, is gebaseerd op grafieken. Hierin kun je dieper in grafieken duiken gids voor de grafiekgegevensstructuur.

Een grafiek implementeren in Golang

Om zelf een datastructuur te implementeren, moet u meestal implementeren objectgeoriënteerd programmeren (OOP) concepten, maar OOP implementeren in Go is niet precies hetzelfde als in andere talen zoals Java en C++.

Go gebruikt structs, typen en interfaces om OOP-concepten te implementeren, en dit is alles wat je nodig hebt om een ​​grafische datastructuur en zijn methoden te implementeren.

Een graaf bestaat uit knopen (of hoekpunten) en randen. Een knooppunt is een entiteit of element in de grafiek. Een voorbeeld van een node is een apparaat op een netwerk of een persoon op een sociaal netwerk. Terwijl een rand een verbinding of relatie is tussen twee knooppunten.

Om een ​​graaf in Go te implementeren, moet u eerst een knooppuntstructuur definiëren waarvan de eigenschap de buren zijn. De buren van een knooppunt zijn de andere knooppunten die direct verbonden zijn met het knooppunt.

In gerichte grafieken hebben randen richtingen, dus alleen de knooppunten waarnaar een bepaald knooppunt verwijst, worden als zijn buren beschouwd. In ongerichte grafieken zijn alle knooppunten die een rand delen met een knooppunt de buren.

De volgende code laat zien hoe de Knooppunt structuur ziet eruit:

type Node struct {
 Neighbors []*Node
}

In dit artikel zal de focus liggen op een ongerichte grafiek. Om echter meer duidelijkheid te verschaffen, is hier wat a Knooppunt struct voor een gerichte graaf kan er als volgt uitzien:

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

Met deze definitie, de Buitenburen slice slaat de knooppunten op waarnaar uitgaande randen zijn vanaf het huidige knooppunt, en de In Buren slice slaat de knooppunten op waarvan er inkomende randen zijn naar het huidige knooppunt.

U implementeert de grafiek met behulp van een kaart van gehele getallen naar knooppunten. Deze kaart dient als de aangrenzende lijst (de gebruikelijke manier om grafieken weer te geven). De sleutel dient als een unieke ID voor een knooppunt, terwijl de waarde het knooppunt is.

De volgende code toont de Grafiek structuur:

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

De integer-sleutel kan ook worden voorgesteld als de waarde van het knooppunt waaraan deze is toegewezen. Hoewel in real-world scenario's uw node een andere gegevensstructuur kan zijn die het profiel van een persoon vertegenwoordigt of iets dergelijks. In dergelijke gevallen zou u de gegevens als een van de eigenschappen van de Node-structuur moeten hebben.

U hebt een functie nodig die als constructor fungeert voor het initialiseren van een nieuwe grafiek. Hierdoor wordt geheugen toegewezen voor de aangrenzende lijst en kunt u knooppunten aan de grafiek toevoegen. De onderstaande code is de definitie van een constructor voor de Grafiek klas:

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

U kunt nu methoden definiëren voor het uitvoeren van verschillende soorten bewerkingen op de grafiek. Er zijn verschillende bewerkingen die u op een grafiek kunt uitvoeren, van het toevoegen van knooppunten tot het maken van randen tussen knooppunten, het zoeken naar knooppunten en meer.

In dit artikel verken je de functies voor het toevoegen van knooppunten en randen aan grafieken, en voor het verwijderen ervan. De volgende code-illustraties zijn de implementaties van de functies voor het uitvoeren van deze bewerkingen.

Een knoop aan de grafiek toevoegen

Om een ​​nieuw knooppunt aan de grafiek toe te voegen, hebt u de invoegfunctie nodig die er als volgt uitziet:

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 functie voegt een nieuw knooppunt toe aan de grafiek met de ID die eraan wordt doorgegeven als een parameter. De functie controleert of er al een knooppunt met dezelfde ID bestaat voordat het aan de grafiek wordt toegevoegd.

Een rand toevoegen aan de grafiek

De volgende belangrijke methode van de grafiekgegevensstructuur is de functie om een ​​rand toe te voegen (dat wil zeggen om een ​​verbinding tussen twee knooppunten tot stand te brengen). Aangezien de grafiek hier ongericht is, hoeft u zich geen zorgen te maken over de richting bij het maken van randen.

Hier is de functie om een ​​rand toe te voegen tussen twee knooppunten in de grafiek:

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

Best makkelijk! De toevoeging van randen in een ongerichte graaf is simpelweg het proces waarbij beide knooppunten buren van elkaar worden. De functie haalt beide knooppunten op door de ID's die eraan zijn doorgegeven en voegt ze beide aan elkaar toe Buren plak.

Een rand uit de grafiek verwijderen

Om een ​​knooppunt uit een grafiek te verwijderen, moet u het uit alle lijsten met buren verwijderen om er zeker van te zijn dat er geen gegevensinconsistenties zijn.

Het proces van het verwijderen van een knooppunt van al zijn buren is hetzelfde als het proces van het verwijderen van randen (of breken verbindingen) tussen de knooppunten, daarom moet u eerst de functie voor het verwijderen van randen definiëren voordat u de ene naar definieert knooppunten verwijderen.

Hieronder vindt u de uitvoering van de verwijderEdge functie:

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 verwijderEdge functie accepteert twee knooppunten als parameters en zoekt naar de index van het tweede (buur)knooppunt in de lijst met buren van het hoofdknooppunt. Het gaat dan door om de buurman te verwijderen knooppunt. Buren met behulp van een techniek genaamd het snijden van de plak.

De verwijdering werkt door de elementen van het segment tot (maar niet inclusief) de opgegeven index en elementen van het segment van na de opgegeven index te nemen en ze samen te voegen. Het element op de opgegeven index laten staan.

In dit geval heb je een ongerichte grafiek, daarom zijn de randen bidirectioneel. Daarom moest je bellen met de verwijderEdge tweemaal in hoofdzaak Edge verwijderen functie om de buur uit de lijst van het knooppunt te verwijderen en vice versa.

Een knooppunt uit de grafiek verwijderen

Zodra u randen kunt verwijderen, kunt u ook knooppunten verwijderen. Hieronder staat de functie om knooppunten uit de grafiek te verwijderen:

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

De functie accepteert de ID van het knooppunt dat u moet verwijderen. Het controleert of het knooppunt bestaat voordat het alle randen verwijdert. Vervolgens wordt het knooppunt uit de grafiek verwijderd met behulp van Go's ingebouwde verwijderen functie.

U kunt ervoor kiezen om meer methoden voor uw grafiek te implementeren, zoals functies om de grafiek te doorlopen met behulp van dept-first search of width-first search, of een functie om de grafiek af te drukken. U kunt altijd methoden aan de structuur toevoegen op basis van uw behoeften.

Houd er ook rekening mee dat grafieken zeer efficiënt zijn, maar als ze niet correct worden gebruikt, ze de structuur van uw applicatie kunnen ruïneren. Als ontwikkelaar moet u weten hoe u datastructuren kiest voor verschillende gebruiksscenario's.

Bouw geoptimaliseerde software met behulp van de juiste gegevensstructuren

Go biedt al een geweldig platform om efficiënte softwaretoepassingen te ontwikkelen, maar als je goed verwaarloost ontwikkelingspraktijken, kan dit verschillende problemen veroorzaken voor de architectuur en prestaties van uw toepassing.

Een belangrijke best practice is het toepassen van de juiste datastructuren, zoals arrays, gekoppelde lijsten en grafieken, voor verschillende behoeften. Hiermee kunt u ervoor zorgen dat uw applicatie correct werkt en hoeft u zich minder zorgen te maken over prestatieknelpunten of storingen die kunnen optreden.