Kā ieviest diagrammas datu struktūru Golangā

Programmatūras nozarē bieži rodas problēmas, kas saistītas ar grafiku. Tehniskās intervijās vai lietojumprogrammu veidošanā, kurās tiek izmantoti grafiki.

Grafiki ir pamata datu struktūras, ko izmanto dažādās lietojumprogrammās, sākot no sociālajiem tīkliem un transporta sistēmām līdz ieteikumu dzinējiem un tīkla analīzei.

Kas ir grafiks un kā jūs varat ieviest grafikus programmā Go?

Kas ir grafiks?

Grafiks ir nelineāra datu struktūra, kas attēlo mezglu (vai virsotņu) kopumu un savienojumus starp tiem (malām). Grafikus plaši izmanto lietojumprogrammās, kas lielā mērā nodarbojas ar savienojumiem, piemēram, datortīkliem, sociālajiem tīkliem un citiem.

Grafiks ir viens no datu struktūras, kas jums jāzina kā programmētājs. Grafiki nodrošina jaudīgu un elastīgu veidu, kā modelēt un analizēt dažādus reālās pasaules scenārijus, un tas padara tos par fundamentālu un galveno datu struktūru datorzinātnēs.

Plašs programmatūras pasaulē izmantoto problēmu risināšanas algoritmu klāsts ir balstīts uz grafikiem. Šajā grafikā varat ienirt dziļāk ceļvedis grafika datu struktūrai.

Grafika ieviešana Golangā

Vairumā gadījumu, lai pats ieviestu datu struktūru, tas ir jāievieš objektorientētā programmēšana (OOP) jēdzieni, bet ieviešot OOP pakalpojumā Go nav tieši tāds pats kā citās valodās, piemēram, Java un C++.

Go izmanto struktūras, tipus un saskarnes, lai ieviestu OOP koncepcijas, un tas ir viss, kas jums nepieciešams, lai ieviestu diagrammas datu struktūru un tās metodes.

Grafs sastāv no mezgliem (vai virsotnēm) un malām. Mezgls ir entītija vai elements diagrammā. Mezgla piemērs ir ierīce tīklā vai persona sociālajā tīklā. Kamēr mala ir savienojums vai attiecības starp diviem mezgliem.

Lai ieviestu grafiku programmā Go, vispirms ir jādefinē mezgla struktūra, kuras īpašums būs tās kaimiņi. Mezgla kaimiņi ir citi mezgli, kas ir tieši savienoti ar mezglu.

Virzītajos grafikos malām ir virzieni, tāpēc tikai tie mezgli, uz kuriem norāda konkrētais mezgls, tiek uzskatīti par tā kaimiņiem. Nevirzītajos grafikos visi mezgli, kuriem ir kopīga mala ar mezglu, ir tā kaimiņi.

Šis kods parāda, kā Mezgls struktūras izskats:

type Node struct {
 Neighbors []*Node
}

Šajā rakstā galvenā uzmanība tiks pievērsta nevirzītam grafikam. Tomēr, lai nodrošinātu labāku skaidrību, šeit ir norādīts, kas a Mezgls virzīta grafika struktūra varētu izskatīties šādi:

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

Izmantojot šo definīciju, ĀrpusKaimiņi slice saglabās mezglus, kuriem ir pašreizējā mezgla izejošās malas, un InNeighbors slice saglabās mezglus, no kuriem pašreizējā mezglā ir ienākošās malas.

Jūs ieviesīsit grafiku, izmantojot veselu skaitļu karti līdz mezgliem. Šī karte kalpo kā blakus vietu saraksts (parastais grafiku attēlošanas veids). Atslēga kalpo kā unikāls mezgla ID, savukārt vērtība būs mezgls.

Šis kods parāda Grafiks struktūra:

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

Vesela skaitļa atslēgu var iedomāties arī kā tā mezgla vērtību, kuram tā ir kartēta. Lai gan reālos scenārijos jūsu mezgls var būt cita datu struktūra, kas atspoguļo personas profilu vai kaut kas līdzīgs. Šādos gadījumos datiem vajadzētu būt vienam no mezgla struktūras rekvizītiem.

Jums ir nepieciešama funkcija, kas darbotos kā konstruktors jauna grafika inicializācijai. Tas piešķirs atmiņu blakus esošo vietu sarakstam un ļaus grafikam pievienot mezglus. Tālāk esošais kods ir konstruktora definīcija Grafiks klase:

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

Tagad varat definēt metodes dažādu veidu operāciju veikšanai grafikā. Ir dažādas darbības, kuras varat veikt grafikā, sākot no mezglu pievienošanas līdz malu izveidošanai starp mezgliem, mezglu meklēšanai un citām.

Šajā rakstā jūs izpētīsit funkcijas mezglu un malu pievienošanai grafikiem, kā arī to noņemšanai. Sekojošās kodu ilustrācijas ir šo darbību veikšanas funkciju realizācijas.

Mezgla pievienošana grafikam

Lai diagrammai pievienotu jaunu mezglu, ir nepieciešama ievietošanas funkcija, kas izskatās šādi:

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 funkcija pievieno diagrammai jaunu mezglu ar ID, kas tam tiek nodots kā parametrs. Funkcija pirms pievienošanas grafikam pārbauda, ​​vai mezgls ar tādu pašu ID jau pastāv.

Malas pievienošana grafikam

Nākamā svarīgā grafika datu struktūras metode ir funkcija pievienot malu (tas ir, izveidot savienojumu starp diviem mezgliem). Tā kā šeit redzamais grafiks ir nevirzīts, tad, veidojot malas, nav jāuztraucas par virzienu.

Šeit ir funkcija, lai pievienotu malu starp diviem diagrammas mezgliem:

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

Diezgan vienkārši! Malu pievienošana nevirzītā grafikā ir vienkārši process, kurā abi mezgli ir viens otram blakus. Funkcija iegūst abus mezglus pēc tai nodotajiem ID un pievieno tos abus viens otram Kaimiņi šķēle.

Malas noņemšana no grafika

Lai noņemtu mezglu no diagrammas, tas ir jānoņem no visiem tā kaimiņu sarakstiem, lai nodrošinātu, ka nav datu pretrunu.

Mezgla noņemšanas process no visiem tā kaimiņiem ir tāds pats kā malu noņemšanas (vai laušanas) process savienojumi) starp mezgliem, tāpēc vispirms ir jādefinē malu noņemšanas funkcija, pirms definējat malu noņemt mezglus.

Zemāk ir aprakstīta īstenošana noņemtEdge 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 noņemtEdge funkcija pieņem divus mezglus kā parametrus un meklē otrā (kaimiņu) mezgla indeksu galvenā mezgla kaimiņu sarakstā. Pēc tam tas iet uz priekšu, lai noņemtu kaimiņu no mezgls. Kaimiņi izmantojot tehniku, ko sauc sagriežot šķēli.

Noņemšana notiek, paņemot šķēles elementus līdz (bet neietverot) norādītajam indeksam, bet šķēluma elementus no norādītā indeksa un savienojot tos. Norādītā indeksa elementa atstāšana ārpusē.

Šajā gadījumā jums ir nevirzīts grafs, tāpēc tā malas ir divvirzienu. Tāpēc jums bija jāzvana noņemtEdge divas reizes galvenajā NoņemtEdge funkcija, lai noņemtu kaimiņu no mezgla saraksta un otrādi.

Mezgla noņemšana no grafika

Kad varat noņemt malas, varat noņemt arī mezglus. Tālāk ir norādīta funkcija mezglu noņemšanai no diagrammas:

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 pieņem tā mezgla ID, kas ir jānoņem. Tas pārbauda, ​​vai mezgls pastāv, pirms tiek noņemtas visas tā malas. Pēc tam tas izdzēš mezglu no diagrammas, izmantojot Go iebūvēto dzēst funkciju.

Varat izvēlēties savā diagrammā ieviest vairāk metožu, piemēram, funkcijas, lai šķērsotu grafiku, izmantojot meklēšanu vispirms vai platuma meklēšanu, vai funkciju grafika drukāšanai. Jūs vienmēr varat pievienot struktūrai metodes atbilstoši savām vajadzībām.

Ņemiet vērā arī to, ka diagrammas ir ļoti efektīvas, taču, ja tās netiek izmantotas pareizi, tās var sabojāt lietojumprogrammas struktūru. Jums kā izstrādātājam jāzina, kā izvēlēties datu struktūras dažādiem lietošanas gadījumiem.

Izveidojiet optimizētu programmatūru, izmantojot pareizās datu struktūras

Go jau nodrošina lielisku platformu, lai izstrādātu efektīvas programmatūras lietojumprogrammas, bet, ja jūs neievērojat labu izstrādes praksē, tas var radīt dažādas problēmas jūsu lietojumprogrammas arhitektūrai un veiktspējai.

Viena svarīga paraugprakse ir piemērotu datu struktūru, piemēram, masīvu, saistīto sarakstu un grafiku, pieņemšana dažādām vajadzībām. Tādējādi varat nodrošināt, ka lietojumprogramma darbojas pareizi, un mazāk jāuztraucas par veiktspējas vājajām vietām vai kļūmēm, kas var rasties.