Grafovi su jedna od najvažnijih struktura podataka koju morate poznavati kao programer. Naučite kako to implementirati u Golangu.
Problemi povezani s grafovima često će vam se susresti u softverskoj industriji. Bilo u tehničkim razgovorima ili prilikom izrade aplikacija koje koriste grafikone.
Grafovi su temeljne podatkovne strukture koje se koriste u raznim aplikacijama, od društvenih mreža i transportnih sustava do mehanizama za preporuke i analize mreže.
Što je graf i kako možete implementirati grafove u Go?
Što je grafikon?
Graf je nelinearna podatkovna struktura koja predstavlja skup čvorova (ili vrhova) i veza između njih (rubova). Grafovi se naširoko koriste u softverskim aplikacijama koje se uvelike bave vezama poput računalnih mreža, društvenih mreža itd.
Graf je jedan od strukture podataka koje biste trebali poznavati kao programer. Grafovi pružaju moćan i fleksibilan način za modeliranje i analizu različitih scenarija iz stvarnog svijeta, što ih čini temeljnom i ključnom strukturom podataka u računalnoj znanosti.
Veliki izbor algoritama za rješavanje problema koji se koriste u svijetu softvera temelji se na grafikonima. U ovome možete dublje zaroniti u grafikone vodič kroz strukturu podataka grafa.
Implementacija grafa u Golangu
U većini slučajeva morate implementirati podatkovnu strukturu sami objektno orijentirano programiranje (OOP) pojmova, ali implementacija OOP-a u Go nije potpuno isti kao što ga imate u drugim jezicima kao što su Java i C++.
Go koristi strukture, tipove i sučelja za implementaciju OOP koncepata, a to je sve što trebate za implementaciju strukture podataka grafa i njenih metoda.
Graf se sastoji od čvorova (ili vrhova) i rubova. Čvor je entitet ili element u grafu. Primjer čvora je uređaj na mreži ili osoba na društvenoj mreži. Dok je rub veza ili odnos između dva čvora.
Da biste implementirali graf u Go, prvo trebate definirati strukturu čvora čije će svojstvo biti njegovi susjedi. Susjedi čvora su drugi čvorovi koji su izravno povezani s čvorom.
U usmjerenim grafovima, rubovi imaju smjerove tako da se samo čvorovi na koje dani čvor pokazuje smatraju njegovim susjedima. Dok su u neusmjerenim grafovima svi čvorovi koji dijele rub s čvorom njegovi susjedi.
Sljedeći kod pokazuje kako se Čvor struktura izgleda:
type Node struct {
Neighbors []*Node
}
U ovom članku fokus će biti na neusmjerenom grafu. Međutim, radi bolje jasnoće, evo što a Čvor struktura za usmjereni graf može izgledati ovako:
type Node struct {
OutNeighbors []*Node // outgoing edges
InNeighbors []*Node // incoming edges
}
S ovom definicijom, OutNeighbors slice će pohraniti čvorove do kojih postoje odlazni rubovi iz trenutnog čvora, i U susjedima slice će pohraniti čvorove iz kojih postoje dolazni rubovi do trenutnog čvora.
Graf ćete implementirati koristeći mapu cijelih brojeva u čvorove. Ova karta služi kao popis susjedstva (uobičajen način predstavljanja grafova). Ključ služi kao jedinstveni ID za čvor, dok će vrijednost biti čvor.
Sljedeći kod prikazuje Grafikon struktura:
type Graph struct {
nodes map[int]*Node
}
Cjelobrojni ključ također se može zamisliti kao vrijednost čvora na koji je preslikan. Iako bi u scenarijima stvarnog svijeta vaš čvor mogao biti druga struktura podataka koja predstavlja profil osobe ili nešto slično. U takvim slučajevima trebali biste imati podatke kao jedno od svojstava strukture čvora.
Trebate funkciju koja će djelovati kao konstruktor za inicijalizaciju novog grafa. Ovo će dodijeliti memoriju za popis susjedstva i omogućiti vam dodavanje čvorova na graf. Kod u nastavku definicija je konstruktora za Grafikon razred:
funcNewGraph() *Graph {
return &Graph{
nodes: make(map[int]*Node),
}
}
Sada možete definirati metode za izvođenje raznih vrsta operacija na grafikonu. Postoje razne operacije koje možete izvesti na grafu, od dodavanja čvorova do stvaranja rubova između čvorova, traženja čvorova i više.
U ovom ćete članku istražiti funkcije za dodavanje čvorova i rubova na grafikone, kao i njihovo uklanjanje. Sljedeće ilustracije koda su implementacije funkcija za izvođenje ovih operacija.
Dodavanje čvora na grafikon
Da biste dodali novi čvor na grafikon, potrebna vam je funkcija umetanja koja izgleda ovako:
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 dodaje novi čvor na grafu s ID-om koji mu je proslijeđen kao parametar. Funkcija provjerava postoji li već čvor s istim ID-om prije nego što ga doda u grafikon.
Dodavanje ruba grafikonu
Sljedeća važna metoda strukture podataka grafa je funkcija za dodavanje ruba (to jest, za stvaranje veze između dva čvora). Budući da je graf ovdje neusmjeren, nema potrebe brinuti o smjeru prilikom stvaranja rubova.
Ovo je funkcija za dodavanje ruba između dva čvora na grafikonu:
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)
}
Prilično jednostavno! Dodavanje bridova u neusmjereni graf je jednostavno proces stvaranja oba čvora susjeda jedan drugome. Funkcija dobiva oba čvora prema ID-ovima koji su joj proslijeđeni i dodaje ih jedan drugome Komšije kriška.
Uklanjanje ruba s grafikona
Da biste uklonili čvor s grafikona, morate ga ukloniti sa svih popisa njegovih susjeda kako biste bili sigurni da nema nedosljednosti podataka.
Proces uklanjanja čvora od svih njegovih susjeda isti je kao postupak uklanjanja rubova (ili lomljenja veze) između čvorova, stoga prvo morate definirati funkciju za uklanjanje rubova prije definiranja one koja će ukloniti čvorove.
U nastavku je implementacija removeEdge funkcija:
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 funkcija prihvaća dva čvora kao parametre i traži indeks drugog (susjednog) čvora na popisu susjeda glavnog čvora. Zatim nastavlja s uklanjanjem susjeda čvor. Komšije pomoću tehnike tzv rezanje kriške.
Uklanjanje funkcionira tako da se elementi isječka do (ali ne uključujući) navedenog indeksa i elementi isječka nakon navedenog indeksa uzimaju i spajaju. Izostavljanje elementa na navedenom indeksu.
U ovom slučaju imate neusmjereni graf, stoga su njegovi rubovi dvosmjerni. Zbog toga ste morali nazvati removeEdge dvaput u glavnom RemoveEdge funkciju za uklanjanje susjeda s popisa čvora i obrnuto.
Uklanjanje čvora s grafa
Nakon što ste u mogućnosti ukloniti rubove, možete ukloniti i čvorove. Ispod je funkcija za uklanjanje čvorova s grafikona:
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")
}
Funkcija prihvaća ID čvora koji trebate ukloniti. Provjerava postoji li čvor prije nego što nastavi s uklanjanjem svih njegovih rubova. Zatim briše čvor s grafikona pomoću Go-ovog ugrađenog izbrisati funkcija.
Možete odabrati implementaciju više metoda za svoj graf, kao što su funkcije za prelazak grafa korištenjem pretraživanja prvo u dubinu ili pretraživanja prvo u širinu, ili funkciju za ispis grafa. Uvijek možete dodati metode strukturi prema svojim potrebama.
Također biste trebali imati na umu da su grafikoni vrlo učinkoviti, ali ako se ne koriste ispravno, mogu uništiti strukturu vaše aplikacije. Morate znati kako odabrati strukture podataka za različite slučajeve upotrebe kao programer.
Izradite optimizirani softver koristeći prave strukture podataka
Go već pruža izvrsnu platformu za razvoj učinkovitih softverskih aplikacija, ali kada zanemarite dobro razvojne prakse, može uzrokovati različite probleme za arhitekturu i izvedbu vaše aplikacije.
Jedna važna najbolja praksa je usvajanje pravih struktura podataka kao što su nizovi, povezani popisi i grafikoni za različite potrebe. Time možete osigurati da vaša aplikacija radi ispravno i manje brinuti o uskim grlima u izvedbi ili kvarovima koji se mogu pojaviti.
