Kaip įdiegti grafiko duomenų struktūrą Golange

Su grafika susijusios problemos dažnai iškils programinės įrangos pramonėje. Ar atliekant techninius pokalbius, ar kuriant programas, kuriose naudojami grafikai.

Grafikai yra pagrindinės duomenų struktūros, naudojamos įvairiose programose, pradedant socialiniais tinklais ir transporto sistemomis iki rekomendacijų variklių ir tinklo analizės.

Kas yra grafikas ir kaip galite įdiegti grafikus Go?

Kas yra Grafas?

Grafas yra nelinijinė duomenų struktūra, vaizduojanti mazgų (arba viršūnių) ir jungčių tarp jų (kraštų) rinkinį. Grafikai plačiai naudojami programinės įrangos programose, kurios labai susijusios su ryšiais, tokiais kaip kompiuterių tinklai, socialiniai tinklai ir kt.

Grafikas yra vienas iš duomenų struktūras, kurias turėtumėte žinoti kaip programuotojas. Grafikai yra galingas ir lankstus būdas modeliuoti ir analizuoti įvairius realaus pasaulio scenarijus, todėl jie yra pagrindinė ir pagrindinė kompiuterių mokslo duomenų struktūra.

Įvairūs problemų sprendimo algoritmai, naudojami programinės įrangos pasaulyje, yra pagrįsti grafikais. Čia galite giliau pasinerti į grafikus grafiko duomenų struktūros vadovas.

Grafo įgyvendinimas Golang

Daugeliu atvejų, norėdami įdiegti duomenų struktūrą patys, turite įdiegti Objektinis programavimas (OOP) sąvokos, bet OOP įdiegimas Go nėra visiškai toks pat, kaip ir kitomis kalbomis, pvz., Java ir C++.

„Go“ naudoja struktūras, tipus ir sąsajas, kad įgyvendintų OOP koncepcijas, ir tai yra viskas, ko jums reikia norint įdiegti grafiko duomenų struktūrą ir jos metodus.

Grafas susideda iš mazgų (arba viršūnių) ir briaunų. Mazgas yra grafiko objektas arba elementas. Mazgo pavyzdys yra įrenginys tinkle arba asmuo socialiniame tinkle. Nors kraštas yra ryšys arba ryšys tarp dviejų mazgų.

Norėdami įdiegti grafiką programoje Go, pirmiausia turite apibrėžti mazgo struktūrą, kurios nuosavybė bus jos kaimynai. Mazgo kaimynai yra kiti mazgai, kurie yra tiesiogiai prijungti prie mazgo.

Nukreiptuose grafikuose briaunos turi kryptis, todėl tik tie mazgai, į kuriuos nurodo duotas mazgas, yra laikomi jo kaimynais. Nenukreiptuose grafikuose visi mazgai, turintys kraštą su mazgu, yra jo kaimynai.

Šis kodas parodo, kaip Mazgas konstrukcija atrodo:

type Node struct {
 Neighbors []*Node
}

Šiame straipsnyje pagrindinis dėmesys bus skiriamas neorientuotam grafikui. Tačiau, siekiant didesnio aiškumo, štai kas a Mazgas nukreipto grafiko struktūra gali atrodyti taip:

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

Su šiuo apibrėžimu, Išorės kaimynai slice saugos mazgus, į kuriuos yra išeinantys dabartinio mazgo kraštai, ir Kaimynuose slice saugos mazgus, iš kurių yra įeinantys kraštai į dabartinį mazgą.

Diagramą įgyvendinsite naudodami sveikųjų skaičių ir mazgų žemėlapį. Šis žemėlapis tarnauja kaip gretimų vietų sąrašas (dažnas grafikų vaizdavimo būdas). Raktas naudojamas kaip unikalus mazgo ID, o reikšmė bus mazgas.

Šis kodas rodo Grafikas struktūra:

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

Sveikasis raktas taip pat gali būti įsivaizduojamas kaip mazgo, su kuriuo jis susietas, reikšmė. Nors realaus pasaulio scenarijuose jūsų mazgas gali būti kitokia duomenų struktūra, atspindinti asmens profilį ar kažkas panašaus. Tokiais atvejais duomenis turėtumėte turėti kaip vieną iš mazgo struktūros savybių.

Jums reikia funkcijos, kuri veiktų kaip konstruktorius inicijuojant naują grafiką. Tai paskirs atmintį gretimų vietų sąrašui ir leis pridėti mazgų prie grafiko. Toliau pateiktas kodas yra konstruktoriaus apibrėžimas Grafikas klasė:

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

Dabar galite apibrėžti metodus, kaip atlikti įvairias operacijas diagramoje. Grafike galite atlikti įvairias operacijas – nuo ​​mazgų pridėjimo iki briaunų tarp mazgų kūrimo, mazgų paieškos ir kt.

Šiame straipsnyje apžvelgsite mazgų ir briaunų įtraukimo į grafikus bei jų pašalinimo funkcijas. Šios kodo iliustracijos yra šių operacijų atlikimo funkcijų įgyvendinimas.

Mazgo pridėjimas prie grafiko

Norėdami pridėti naują mazgą prie grafiko, jums reikia įterpimo funkcijos, kuri atrodo taip:

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 grafike prideda naują mazgą su ID, kuris jam perduotas kaip parametras. Funkcija patikrina, ar mazgas su tuo pačiu ID jau yra prieš įtraukdamas jį į grafiką.

Krašto pridėjimas prie grafiko

Kitas svarbus grafiko duomenų struktūros metodas yra funkcija pridėti kraštą (ty sukurti ryšį tarp dviejų mazgų). Kadangi čia pateiktas grafikas yra neorientuotas, kuriant briaunas nereikia jaudintis dėl krypties.

Čia yra funkcija pridėti kraštą tarp dviejų grafiko mazgų:

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

Gana paprasta! Nenukreipto grafiko briaunų pridėjimas yra tiesiog procesas, kai abu mazgai tampa vienas kito kaimynais. Funkcija gauna abu mazgus pagal jai perduotus ID ir abu juos prideda vienas prie kito Kaimynai gabalas.

Krašto pašalinimas iš grafiko

Norėdami pašalinti mazgą iš grafiko, turite jį pašalinti iš visų jo kaimynų sąrašų, kad įsitikintumėte, jog nėra duomenų neatitikimų.

Mazgo pašalinimo iš visų kaimynų procesas yra toks pat kaip ir kraštų pašalinimo (arba sulaužymo jungtys) tarp mazgų, todėl pirmiausia turite apibrėžti kraštų pašalinimo funkciją prieš apibrėždami kraštų pašalinti mazgus.

Žemiau pateikiamas įgyvendinimas pašalinti kraštą 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 pašalinti kraštą funkcija priima du mazgus kaip parametrus ir pagrindinio mazgo kaimynų sąraše ieško antrojo (kaimyno) mazgo indekso. Tada jis eina į priekį, kad pašalintų kaimyną mazgas. Kaimynai naudojant techniką, vadinamą pjaustant griežinėlį.

Pašalinimas vyksta paimant pjūvio elementus iki nurodyto indekso (bet neįskaitant), o po nurodyto indekso - skilties elementus ir juos sujungiant. Nurodyto indekso elemento nepalikimas.

Šiuo atveju jūs turite neorientuotą grafą, todėl jo kraštai yra dvikrypčiai. Štai kodėl jūs turėjote paskambinti pašalinti kraštą du kartus iš esmės Pašalinti kraštą funkcija pašalinti kaimyną iš mazgo sąrašo ir atvirkščiai.

Mazgo pašalinimas iš grafiko

Kai tik galėsite pašalinti kraštus, taip pat galite pašalinti mazgus. Žemiau yra funkcija, skirta pašalinti mazgus iš grafiko:

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 priima mazgo, kurį turite pašalinti, ID. Jis patikrina, ar mazgas egzistuoja, prieš pašalindamas visus jo kraštus. Tada jis ištrina mazgą iš grafiko, naudodamas įmontuotą Go Ištrinti funkcija.

Galite pasirinkti savo diagramoje įdiegti daugiau metodų, pvz., funkcijas, skirtas grafike eiti naudojant paiešką pagal skyrių arba paiešką pagal plotį, arba grafiko spausdinimo funkciją. Jūs visada galite pridėti metodus prie struktūros pagal savo poreikius.

Taip pat turėtumėte atkreipti dėmesį į tai, kad grafikai yra labai veiksmingi, tačiau netinkamai naudojami gali sugadinti programos struktūrą. Jūs, kaip kūrėjas, turite žinoti, kaip pasirinkti duomenų struktūras įvairiems naudojimo atvejams.

Kurkite optimizuotą programinę įrangą naudodami tinkamas duomenų struktūras

„Go“ jau yra puiki platforma efektyvioms programinės įrangos programoms kurti, bet kai nepaisysite gero kūrimo praktikos, tai gali sukelti įvairių problemų jūsų programos architektūrai ir našumui.

Viena iš svarbių geriausių praktikų yra tinkamų duomenų struktūrų, pvz., masyvų, susietų sąrašų ir grafikų, pritaikymas skirtingiems poreikiams. Taip galite užtikrinti, kad jūsų programa veiktų tinkamai, ir mažiau nerimauti dėl galimų našumo kliūčių ar gedimų.