Ako implementovať štruktúru údajov grafu v Golang

Problémy súvisiace s grafmi sa často objavia v softvérovom priemysle. Či už pri technických pohovoroch alebo pri vytváraní aplikácií, ktoré využívajú grafy.

Grafy sú základné dátové štruktúry používané v rôznych aplikáciách, od sociálnych sietí a dopravných systémov až po nástroje odporúčaní a sieťovú analýzu.

Čo je to graf a ako môžete implementovať grafy v Go?

Čo je to graf?

Graf je nelineárna dátová štruktúra, ktorá predstavuje kolekciu uzlov (alebo vrcholov) a spojení medzi nimi (hranami). Grafy sa široko používajú v softvérových aplikáciách, ktoré sa intenzívne zaoberajú prepojeniami, ako sú počítačové siete, sociálne siete a ďalšie.

Graf je jedným z dátové štruktúry, ktoré by ste mali poznať ako programátor. Grafy poskytujú výkonný a flexibilný spôsob modelovania a analýzy rôznych scenárov reálneho sveta, čo z nich robí základnú a základnú dátovú štruktúru v informatike.

Široká škála algoritmov na riešenie problémov používaných vo svete softvéru je založená na grafoch. V tomto sa môžete hlbšie ponoriť do grafov sprievodca štruktúrou údajov grafu.

Implementácia grafu v Golangu

Ak chcete implementovať dátovú štruktúru sami, musíte ju väčšinou implementovať objektovo orientované programovanie (OOP) koncepty, ale implementácia OOP v Go nie je úplne rovnaký ako v iných jazykoch, ako sú Java a C++.

Go používa štruktúry, typy a rozhrania na implementáciu konceptov OOP a to je všetko, čo potrebujete na implementáciu grafovej dátovej štruktúry a jej metód.

Graf sa skladá z uzlov (alebo vrcholov) a hrán. Uzol je entita alebo prvok v grafe. Príkladom uzla je zariadenie v sieti alebo osoba na sociálnej sieti. Zatiaľ čo hrana je spojenie alebo vzťah medzi dvoma uzlami.

Ak chcete implementovať graf v Go, musíte najprv definovať štruktúru uzla, ktorej vlastnosťou budú jej susedia. Susedmi uzla sú ostatné uzly, ktoré sú priamo spojené s uzlom.

V orientovaných grafoch majú hrany smer, takže iba uzly, na ktoré daný uzol ukazuje, sa považujú za jeho susedov. Zatiaľ čo v neorientovaných grafoch sú všetky uzly, ktoré zdieľajú hranu s uzlom, jeho susedmi.

Nasledujúci kód ukazuje, ako Uzol štruktúra vyzerá:

type Node struct {
 Neighbors []*Node
}

V tomto článku sa zameriame na neorientovaný graf. Pre lepšiu prehľadnosť však uvádzame, čo a Uzol štruktúra pre orientovaný graf môže vyzerať takto:

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

S touto definíciou, OutNeighbors Slice uloží uzly, ku ktorým existujú výstupné hrany z aktuálneho uzla, a InNeighbors slice uloží uzly, z ktorých prichádzajú hrany do aktuálneho uzla.

Graf implementujete pomocou mapy celých čísel do uzlov. Táto mapa slúži ako zoznam susedstva (bežný spôsob reprezentácie grafov). Kľúč slúži ako jedinečné ID pre uzol, pričom hodnotou bude uzol.

Nasledujúci kód zobrazuje Graf štruktúra:

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

Celočíselný kľúč si možno predstaviť aj ako hodnotu uzla, na ktorý je mapovaný. Aj keď v scenároch reálneho sveta môže byť vaším uzlom iná dátová štruktúra predstavujúca profil osoby alebo niečo podobné. V takýchto prípadoch by ste mali mať údaje ako jednu z vlastností štruktúry uzla.

Potrebujete funkciu, ktorá bude pôsobiť ako konštruktor na inicializáciu nového grafu. Tým sa pridelí pamäť pre zoznam susediacich miest a umožní vám pridávať uzly do grafu. Nižšie uvedený kód je definícia konštruktora pre Graf trieda:

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

Teraz môžete definovať metódy na vykonávanie rôznych druhov operácií s grafom. Existujú rôzne operácie, ktoré môžete vykonávať na grafe, od pridávania uzlov po vytváranie hrán medzi uzlami, vyhľadávanie uzlov a ďalšie.

V tomto článku preskúmate funkcie na pridávanie uzlov a hrán do grafov, ako aj ich odstraňovanie. Nasledujúce ilustrácie kódu predstavujú implementácie funkcií na vykonávanie týchto operácií.

Pridanie uzla do grafu

Ak chcete do grafu pridať nový uzol, potrebujete funkciu vkladania, ktorá vyzerá takto:

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 funkcia pridá do grafu nový uzol s ID, ktoré mu bolo odovzdané ako parameter. Funkcia pred pridaním do grafu skontroluje, či už existuje uzol s rovnakým ID.

Pridanie okraja do grafu

Ďalšou dôležitou metódou dátovej štruktúry grafu je funkcia pridania hrany (teda vytvorenie spojenia medzi dvoma uzlami). Keďže je tu neorientovaný graf, netreba sa pri vytváraní hrán obávať smeru.

Tu je funkcia na pridanie hrany medzi dva uzly v grafe:

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

Celkom jednoduché! Pridanie hrán v neorientovanom grafe je jednoducho proces, pri ktorom sú oba uzly susedné. Funkcia získa oba uzly pomocou ID, ktoré jej boli odovzdané, a pripojí ich k sebe navzájom Susedia plátok.

Odstránenie okraja z grafu

Ak chcete odstrániť uzol z grafu, musíte ho odstrániť zo všetkých zoznamov susedov, aby ste sa uistili, že neexistujú žiadne nezrovnalosti v údajoch.

Proces odstraňovania uzla od všetkých jeho susedov je rovnaký ako proces odstraňovania hrán (alebo lámania spojenia) medzi uzlami, preto musíte najskôr definovať funkciu na odstránenie hrán pred definovaním jednej do odstrániť uzly.

Nižšie je uvedená implementácia removeEdge funkcia:

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 funkcia akceptuje dva uzly ako parametre a hľadá index druhého (susedného) uzla v zozname susedov hlavného uzla. Potom ide o odstránenie suseda uzol. Susedia pomocou techniky tzv krájanie plátku.

Odstránenie funguje tak, že sa prvky rezu prevezmú až po (ale nezahŕňa) zadaný index a prvky rezu za zadaným indexom a zreťazí sa. Ponechanie prvku na zadanom indexe mimo.

V tomto prípade máte neorientovaný graf, preto sú jeho okraje obojsmerné. Preto ste museli zavolať removeEdge dvakrát v hlavnom RemoveEdge funkcia na odstránenie suseda zo zoznamu uzla a naopak.

Odstránenie uzla z grafu

Keď budete môcť odstrániť okraje, môžete odstrániť aj uzly. Nižšie je uvedená funkcia na odstránenie uzlov z grafu:

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

Funkcia akceptuje ID uzla, ktorý potrebujete odstrániť. Pred odstránením všetkých jeho okrajov skontroluje, či uzol existuje. Potom vymaže uzol z grafu pomocou vstavaného Go vymazať funkciu.

Môžete si vybrať implementáciu viacerých metód pre váš graf, ako sú funkcie na prechádzanie grafom pomocou vyhľadávania na prvom mieste alebo vyhľadávania na šírku, alebo funkcie na tlač grafu. Do štruktúry môžete vždy pridať metódy podľa svojich potrieb.

Mali by ste tiež poznamenať, že grafy sú veľmi efektívne, ale ak sa nepoužívajú správne, môžu zničiť štruktúru vašej aplikácie. Musíte vedieť, ako si ako vývojár vybrať dátové štruktúry pre rôzne prípady použitia.

Vytvárajte optimalizovaný softvér pomocou správnych dátových štruktúr

Go už poskytuje skvelú platformu na vývoj efektívnych softvérových aplikácií, ale keď zanedbáte dobré vývojových postupov, môže to spôsobiť rôzne problémy pre architektúru a výkon vašej aplikácie.

Jedným z dôležitých osvedčených postupov je prijatie správnych dátových štruktúr, ako sú polia, prepojené zoznamy a grafy, pre rôzne potreby. Vďaka tomu môžete zaistiť, aby vaša aplikácia fungovala správne, a nemusíte sa obávať prekážok výkonu alebo porúch, ktoré môžu nastať.