Cum se implementează structura datelor grafice în Golang

Problemele legate de grafice îți vor apărea adesea în industria software-ului. Fie la interviuri tehnice, fie la construirea de aplicații care folosesc grafice.

Graficele sunt structuri de date fundamentale utilizate în diverse aplicații, de la rețelele sociale și sistemele de transport până la motoare de recomandare și analiza rețelei.

Ce este un grafic și cum puteți implementa grafice în Go?

Ce este un grafic?

Un graf este o structură de date neliniară care reprezintă o colecție de noduri (sau vârfuri) și conexiuni între ele (margini). Graficele sunt utilizate pe scară largă în aplicațiile software care se ocupă în mare măsură de conexiuni precum rețele de computere, rețele sociale și multe altele.

Un grafic este unul dintre structurile de date pe care ar trebui să le cunoașteți ca programator. Graficele oferă o modalitate puternică și flexibilă de a modela și analiza diferite scenarii din lumea reală, iar acest lucru le face o structură de date fundamentală și de bază în informatică.

O mare varietate de algoritmi de rezolvare a problemelor utilizați în lumea software se bazează pe grafice. Puteți face o scufundare mai profundă în grafice în aceasta ghid pentru structura datelor grafice.

Implementarea unui grafic în Golang

De cele mai multe ori, pentru a implementa singur o structură de date, trebuie să o implementați programare orientată pe obiecte (OOP) concepte, dar implementarea OOP în Go nu este exact la fel ca și în alte limbi precum Java și C++.

Go utilizează structuri, tipuri și interfețe pentru a implementa concepte OOP și acestea sunt tot ce aveți nevoie pentru a implementa o structură de date grafică și metodele acesteia.

Un grafic este format din noduri (sau vârfuri) și muchii. Un nod este o entitate sau un element din grafic. Un exemplu de nod este un dispozitiv dintr-o rețea sau o persoană dintr-o rețea socială. În timp ce o margine este o conexiune sau o relație între două noduri.

Pentru a implementa un graf în Go, mai întâi trebuie să definiți o structură de nod a cărei proprietate va fi vecină. Vecinii unui nod sunt celelalte noduri care sunt conectate direct la nod.

În graficele direcționate, muchiile au direcții, astfel încât numai nodurile către care indică un nod dat sunt considerate vecine. În timp ce în graficele nedirecționate, toate nodurile care împărtășesc o margine cu un nod sunt vecine.

Următorul cod demonstrează modul în care Nodul struct arată:

type Node struct {
 Neighbors []*Node
}

În acest articol, accentul se va pune pe un grafic nedirecționat. Cu toate acestea, pentru a oferi o claritate mai bună, iată ce a Nodul structura pentru un grafic direcționat ar putea arăta astfel:

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

Cu această definiție, OutNeighbors slice va stoca nodurile la care există margini de ieșire de la nodul curent și În vecini slice va stoca nodurile de la care există margini de intrare către nodul curent.

Veți implementa graficul folosind o hartă de numere întregi la noduri. Această hartă servește drept lista adiacentei (modul comun de reprezentare a graficelor). Cheia servește ca un ID unic pentru un nod, în timp ce valoarea va fi nodul.

Următorul cod arată Grafic structura:

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

Cheia întreagă poate fi imaginată și ca valoarea nodului la care este mapată. Deși în scenarii din lumea reală, nodul dvs. ar putea fi o structură de date diferită care reprezintă profilul unei persoane sau ceva similar. În astfel de cazuri, ar trebui să aveți datele ca una dintre proprietățile structurii Node.

Aveți nevoie de o funcție care să acționeze ca un constructor pentru inițializarea unui nou grafic. Aceasta va aloca memorie pentru lista de adiacență și vă va permite să adăugați noduri la grafic. Codul de mai jos este definiția unui constructor pentru Grafic clasă:

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

Acum puteți defini metode pentru efectuarea diferitelor tipuri de operații pe grafic. Există diverse operații pe care le puteți efectua pe un grafic, de la adăugarea de noduri până la crearea de muchii între noduri, căutarea nodurilor și multe altele.

În acest articol, veți explora funcțiile pentru adăugarea de noduri și margini la grafice, precum și pentru eliminarea acestora. Următoarele ilustrații de cod sunt implementări ale funcțiilor pentru efectuarea acestor operații.

Adăugarea unui nod la grafic

Pentru a adăuga un nou nod la grafic, aveți nevoie de funcția de inserare care arată astfel:

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 funcția adaugă un nou nod pe grafic cu ID-ul transmis ca parametru. Funcția verifică dacă un nod cu același ID există deja înainte de a-l adăuga la grafic.

Adăugarea unei margini la grafic

Următoarea metodă importantă a structurii de date grafice este funcția de a adăuga o margine (adică de a crea o conexiune între două noduri). Deoarece graficul de aici este unul nedirecționat, nu este nevoie să vă faceți griji cu privire la direcție atunci când creați muchii.

Iată funcția de a adăuga o margine între două noduri de pe grafic:

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

Destul de simplu! Adăugarea muchiilor într-un graf nedirecționat este pur și simplu procesul de a face ambele noduri vecine unul cu celălalt. Funcția primește ambele noduri prin ID-urile transmise și le adaugă pe ambele unul celuilalt Vecini felie.

Eliminarea unei margini din grafic

Pentru a elimina un nod dintr-un grafic, trebuie să-l eliminați din listele tuturor vecinilor săi pentru a vă asigura că nu există inconsecvențe de date.

Procesul de eliminare a unui nod de la toți vecinii săi este același cu procesul de îndepărtare a marginilor (sau de rupere conexiuni) între noduri, de aceea trebuie să definiți mai întâi funcția pentru eliminarea marginilor înainte de a o defini pe cea pentru eliminați nodurile.

Mai jos este implementarea removeEdge funcţie:

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 removeEdge funcția acceptă două noduri ca parametri și caută indexul celui de-al doilea nod (vecin) în lista de vecini a nodului principal. Apoi merge înainte pentru a elimina vecinul din nodul. Vecini folosind o tehnică numită felierea feliei.

Eliminarea funcționează prin preluarea elementelor feliei până la (dar fără a include) indexul specificat și elemente ale feliei de după indexul specificat și concatenarea acestora. Lăsând elementul la indexul specificat.

În acest caz, aveți un grafic nedirecționat, prin urmare marginile sale sunt bidirecționale. Acesta este motivul pentru care a trebuit să suni la removeEdge de două ori în principal RemoveEdge funcția de a elimina vecinul din lista nodului și invers.

Eliminarea unui nod din grafic

Odată ce puteți elimina marginile, puteți elimina și nodurile. Mai jos este funcția de eliminare a nodurilor din grafic:

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

Funcția acceptă ID-ul nodului pe care trebuie să îl eliminați. Verifică dacă nodul există înainte de a continua să-i elimine toate marginile. Apoi șterge nodul din grafic folosind Go-ul încorporat șterge funcţie.

Puteți alege să implementați mai multe metode pentru graficul dvs., cum ar fi funcții pentru a parcurge graficul folosind căutarea dept-first sau breadth-first search, sau o funcție pentru a tipări graficul. Puteți adăuga oricând metode la struct în funcție de nevoile dvs.

De asemenea, ar trebui să rețineți că graficele sunt foarte eficiente, dar dacă nu sunt utilizate corect, vă pot distruge structura aplicației. Trebuie să știi cum să alegi structuri de date pentru diferite cazuri de utilizare ca dezvoltator.

Creați software optimizat folosind structurile de date potrivite

Go oferă deja o platformă excelentă pentru a dezvolta aplicații software eficiente, dar când neglijezi binele practicilor de dezvoltare, poate cauza diferite probleme pentru arhitectura și performanța aplicației dvs.

O bună practică importantă este adoptarea structurilor de date potrivite, cum ar fi matrice, liste legate și grafice, pentru diferite nevoi. Cu aceasta, vă puteți asigura că aplicația dvs. funcționează corect și vă puteți îngrijora mai puțin cu privire la blocajele de performanță sau eșecurile care pot apărea.