Come implementare la struttura dei dati del grafico in Golang

I problemi relativi ai grafici ti verranno spesso incontro nell'industria del software. Sia nelle interviste tecniche che durante la creazione di applicazioni che utilizzano i grafici.

I grafici sono strutture di dati fondamentali utilizzate in varie applicazioni, che vanno dai social network e dai sistemi di trasporto ai motori di raccomandazione e all'analisi di rete.

Che cos'è un grafico e come puoi implementare i grafici in Go?

Cos'è un grafico?

Un grafico è una struttura di dati non lineare che rappresenta una raccolta di nodi (o vertici) e connessioni tra di essi (bordi). I grafici sono ampiamente utilizzati nelle applicazioni software che si occupano pesantemente di connessioni come reti di computer, social network e altro ancora.

Un grafico è uno di le strutture dati che dovresti conoscere come programmatore. I grafici forniscono un modo potente e flessibile per modellare e analizzare vari scenari del mondo reale, e questo li rende una struttura di dati fondamentale e fondamentale nell'informatica.

Un'ampia varietà di algoritmi di risoluzione dei problemi utilizzati nel mondo del software si basano su grafici. Puoi fare un tuffo più profondo nei grafici in questo guida alla struttura dei dati del grafico.

Implementazione di un grafico in Golang

La maggior parte delle volte per implementare una struttura dati da soli, è necessario implementare programmazione orientata agli oggetti (OOP) concetti, ma implementare OOP in Go non è esattamente lo stesso che hai in altri linguaggi come Java e C++.

Go utilizza strutture, tipi e interfacce per implementare concetti OOP, e questi sono tutto ciò che serve per implementare una struttura di dati del grafico e i suoi metodi.

Un grafo è costituito da nodi (o vertici) e spigoli. Un nodo è un'entità o un elemento nel grafico. Un esempio di nodo è un dispositivo su una rete o una persona su un social network. Mentre un bordo è una connessione o relazione tra due nodi.

Per implementare un grafico in Go, devi prima definire una struttura del nodo la cui proprietà sarà i suoi vicini. I vicini di un nodo sono gli altri nodi direttamente connessi al nodo.

Nei grafici orientati, i bordi hanno direzioni, quindi solo i nodi a cui punta un dato nodo sono considerati i suoi vicini. Mentre nei grafici non orientati, tutti i nodi che condividono un bordo con un nodo sono i suoi vicini.

Il codice seguente illustra come il Nodo struct sembra:

type Node struct {
 Neighbors []*Node
}

In questo articolo, l'attenzione si concentrerà su un grafico non orientato. Tuttavia, per fornire maggiore chiarezza, ecco cosa a Nodo struct per un grafico diretto potrebbe essere simile a:

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

Con questa definizione il OutNeighbours slice memorizzerà i nodi a cui sono presenti bordi in uscita dal nodo corrente e il file Nei vicini slice memorizzerà i nodi da cui ci sono bordi in entrata al nodo corrente.

Implementerai il grafico utilizzando una mappa di numeri interi in nodi. Questa mappa funge da lista di adiacenza (il modo comune di rappresentare i grafici). La chiave funge da ID univoco per un nodo, mentre il valore sarà il nodo.

Il codice seguente mostra il Grafico struttura:

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

La chiave intera può anche essere immaginata come il valore del nodo a cui è mappata. Sebbene negli scenari del mondo reale, il tuo nodo potrebbe essere una struttura dati diversa che rappresenta il profilo di una persona o qualcosa di simile. In tali casi, dovresti avere i dati come una delle proprietà della struttura Node.

È necessaria una funzione che funga da costruttore per l'inizializzazione di un nuovo grafico. Ciò allocherà memoria per l'elenco di adiacenza e consentirà di aggiungere nodi al grafico. Il codice seguente è la definizione di un costruttore per il Grafico classe:

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

È ora possibile definire metodi per eseguire vari tipi di operazioni sul grafico. Esistono varie operazioni che è possibile eseguire su un grafico, dall'aggiunta di nodi alla creazione di archi tra i nodi, alla ricerca di nodi e altro ancora.

In questo articolo esplorerai le funzioni per aggiungere nodi e bordi ai grafici, oltre a rimuoverli. Le seguenti illustrazioni di codice sono le implementazioni delle funzioni per l'esecuzione di queste operazioni.

Aggiunta di un nodo al grafico

Per aggiungere un nuovo nodo al grafico, è necessaria la funzione di inserimento simile a questa:

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

IL AddNode La funzione aggiunge un nuovo nodo sul grafico con l'ID passato come parametro. La funzione controlla se esiste già un nodo con lo stesso ID prima di aggiungerlo al grafico.

Aggiunta di un bordo al grafico

Il prossimo metodo importante della struttura dei dati del grafico è la funzione per aggiungere un bordo (ovvero, per creare una connessione tra due nodi). Poiché il grafico qui è non orientato, non è necessario preoccuparsi della direzione durante la creazione dei bordi.

Ecco la funzione per aggiungere un bordo tra due nodi sul grafico:

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

Abbastanza semplice! L'aggiunta di bordi in un grafo non orientato è semplicemente il processo di rendere entrambi i nodi vicini l'uno all'altro. La funzione ottiene entrambi i nodi in base agli ID che le sono stati passati e li accoda entrambi l'uno all'altro Vicinato fetta.

Rimozione di un bordo dal grafico

Per rimuovere un nodo da un grafico, è necessario rimuoverlo da tutti gli elenchi dei suoi vicini per assicurarsi che non vi siano incoerenze nei dati.

Il processo di rimozione di un nodo da tutti i suoi vicini è lo stesso del processo di rimozione dei bordi (o rottura connessioni) tra i nodi, quindi è necessario definire la funzione per rimuovere gli spigoli prima di definire quella a rimuovere i nodi.

Di seguito è riportata l'implementazione del removeEdge funzione:

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

IL removeEdge La funzione accetta due nodi come parametri e cerca l'indice del secondo nodo (vicino) nell'elenco dei nodi vicini del nodo principale. Quindi va avanti per rimuovere il vicino da nodo. Vicinato utilizzando una tecnica chiamata affettare la fetta.

La rimozione funziona prendendo gli elementi della sezione fino a (ma non includendo) l'indice specificato e gli elementi della sezione dopo l'indice specificato e concatenandoli. Lasciando l'elemento all'indice specificato fuori.

In questo caso, hai un grafico non orientato, quindi i suoi bordi sono bidirezionali. Questo è il motivo per cui hai dovuto chiamare il removeEdge due volte nel principale Rimuovibordo funzione per rimuovere il vicino dall'elenco dei nodi e viceversa.

Rimozione di un nodo dal grafico

Una volta che sei in grado di rimuovere i bordi, puoi anche rimuovere i nodi. Di seguito è riportata la funzione per rimuovere i nodi dal grafico:

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

La funzione accetta l'ID del nodo che devi rimuovere. Controlla se il nodo esiste prima di rimuovere tutti i suoi bordi. Quindi elimina il nodo dal grafico utilizzando l'integrato di Go eliminare funzione.

Puoi scegliere di implementare più metodi per il tuo grafico, ad esempio funzioni per attraversare il grafico utilizzando la ricerca dept-first o la ricerca in ampiezza o una funzione per stampare il grafico. Puoi sempre aggiungere metodi alla struttura in base alle tue esigenze.

Dovresti anche notare che i grafici sono molto efficienti ma se non usati correttamente possono rovinare la struttura della tua applicazione. Devi sapere come scegliere le strutture dati per diversi casi d'uso come sviluppatore.

Crea software ottimizzato utilizzando le giuste strutture dati

Go fornisce già un'ottima piattaforma per sviluppare applicazioni software efficienti, ma quando trascuri il bene pratiche di sviluppo, può causare diversi problemi all'architettura e alle prestazioni dell'applicazione.

Un'importante best practice consiste nell'adottare le giuste strutture di dati come array, elenchi collegati e grafici, per esigenze diverse. Con questo, puoi assicurarti che la tua applicazione funzioni correttamente e preoccuparti meno dei colli di bottiglia delle prestazioni o degli errori che possono verificarsi.