A grafikon adatszerkezet megvalósítása Golangban

A grafikonnal kapcsolatos problémák gyakran előfordulnak a szoftveriparban. Akár műszaki interjúk során, akár grafikonokat használó alkalmazások készítésekor.

A grafikonok alapvető adatstruktúrák, amelyeket különféle alkalmazásokban használnak, a közösségi hálózatoktól és a közlekedési rendszerektől kezdve az ajánlómotorokig és a hálózatelemzésig.

Mi az a grafikon, és hogyan lehet grafikonokat megvalósítani a Go-ban?

Mi az a grafikon?

A gráf egy nemlineáris adatstruktúra, amely csomópontok (vagy csúcsok) és a köztük lévő kapcsolatok (élek) gyűjteményét reprezentálja. A grafikonokat széles körben használják olyan szoftveralkalmazásokban, amelyek nagymértékben foglalkoznak olyan kapcsolatokkal, mint a számítógépes hálózatok, a közösségi hálózatok stb.

A grafikon az egyik az adatstruktúrákat, amelyeket ismernie kell mint programozó. A grafikonok hatékony és rugalmas módot biztosítanak különféle valós forgatókönyvek modellezésére és elemzésére, és ez a számítástechnika alapvető és alapvető adatszerkezetévé teszi őket.

A szoftvervilágban használt problémamegoldó algoritmusok széles skálája gráfokon alapul. Ebben mélyebben bele lehet merülni a grafikonokba útmutató a grafikon adatszerkezetéhez.

Grafikon megvalósítása Golangban

A legtöbb esetben egy adatstruktúra önálló megvalósításához meg kell valósítania objektum-orientált programozás (OOP) fogalmak, de az OOP megvalósítása a Go-ban nem pontosan ugyanaz, mint más nyelveken, mint például a Java és a C++.

A Go struktúrákat, típusokat és interfészeket használ az OOP-koncepciók megvalósításához, és ez minden, amire szüksége van egy gráf adatstruktúra és metódusainak megvalósításához.

A gráf csomópontokból (vagy csúcsokból) és élekből áll. A csomópont egy entitás vagy elem a gráfban. Csomópontra példa egy eszköz a hálózaton vagy egy személy a közösségi hálózaton. Míg az él egy kapcsolat vagy kapcsolat két csomópont között.

Egy gráf Go programban való megvalósításához először meg kell határoznia egy csomóponti struktúrát, amelynek tulajdonságai a szomszédai lesznek. Egy csomópont szomszédai a többi csomópont, amelyek közvetlenül kapcsolódnak a csomóponthoz.

Az irányított gráfokban az éleknek irányai vannak, így csak azokat a csomópontokat tekintjük szomszédainak, amelyekre egy adott csomópont mutat. Míg az irányítatlan gráfokban minden csomópont, amely egy élen osztozik egy csomóponttal, szomszédja.

A következő kód bemutatja, hogyan a Csomópont a szerkezet kinézete:

type Node struct {
 Neighbors []*Node
}

Ebben a cikkben a hangsúly egy irányítatlan grafikon lesz. A jobb áttekinthetőség érdekében azonban íme, mi a Csomópont Az irányított gráf szerkezete így nézhet ki:

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

Ezzel a meghatározással a OutNeighbors slice tárolja azokat a csomópontokat, amelyeknek az aktuális csomópontból kimenő élei vannak, és a InNeighbors A slice tárolja azokat a csomópontokat, amelyekről az aktuális csomóponthoz bejövő élek vannak.

A grafikont egész számok csomópontokhoz való leképezése segítségével fogja megvalósítani. Ez a térkép szolgál a szomszédsági lista (a gráfok ábrázolásának általános módja). A kulcs a csomópont egyedi azonosítójaként szolgál, míg az érték a csomópont lesz.

A következő kód mutatja a Grafikon struktúra:

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

Az egész kulcsot annak a csomópontnak az értékeként is elképzelhetjük, amelyhez hozzá van rendelve. Bár valós helyzetekben a csomópont lehet egy másik adatstruktúra, amely egy személy profilját reprezentálja, vagy valami hasonló. Ilyen esetekben az adatoknak a Node struktúra egyik tulajdonságaként kell szerepelniük.

Szüksége van egy függvényre, amely konstruktorként működik egy új gráf inicializálásához. Ez memóriát foglal le a szomszédsági listához, és lehetővé teszi csomópontok hozzáadását a grafikonhoz. Az alábbi kód a konstruktor definíciója a Grafikon osztály:

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

Most már meghatározhat módszereket a grafikonon végzett különféle műveletek végrehajtására. Különféle műveletek végezhetők el a grafikonon, a csomópontok hozzáadásától a csomópontok közötti élek létrehozásáig, a csomópontok kereséséig stb.

Ebben a cikkben megismerheti a csomópontok és élek gráfokhoz való hozzáadásának, valamint azok eltávolításának függvényeit. A következő kódillusztrációk az e műveletek végrehajtásához szükséges funkciók megvalósításait mutatják be.

Csomópont hozzáadása a grafikonhoz

Ha új csomópontot szeretne hozzáadni a grafikonhoz, a következőképpen néz ki:

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

A AddNode függvény hozzáad egy új csomópontot a gráfhoz, amelynek paraméterként átadja az azonosítót. A függvény ellenőrzi, hogy létezik-e már azonos azonosítójú csomópont, mielőtt hozzáadná a gráfhoz.

Él hozzáadása a grafikonhoz

A gráf adatszerkezetének következő fontos módszere az él hozzáadásának (vagyis két csomópont közötti kapcsolat létrehozásának) funkciója. Mivel a gráf itt egy irányítatlan, nem kell aggódni az irány miatt az élek létrehozásakor.

Íme a függvény, amellyel a grafikon két csomópontja közé élt adhatunk:

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

Elég egyszerű! Az élek összeadása egy irányítatlan gráfban egyszerűen az a folyamat, amikor mindkét csomópont szomszédossá válik. A függvény mindkét csomópontot megkapja a neki átadott azonosítók alapján, és mindkettőt hozzáfűzi egymáshoz Szomszédok szelet.

Él eltávolítása a grafikonról

Ha el szeretne távolítani egy csomópontot a grafikonról, el kell távolítania azt az összes szomszédos listáról, hogy biztosítsa az adatok inkonzisztenciáját.

Egy csomópont eltávolításának folyamata az összes szomszédjából ugyanaz, mint az élek eltávolításának (vagy törésének folyamata kapcsolatok) a csomópontok között, ezért először meg kell határoznia az élek eltávolításának funkcióját, mielőtt meghatározná az éleket. távolítsa el a csomópontokat.

Az alábbiakban bemutatjuk a végrehajtását távolítsa el az élt funkció:

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

A távolítsa el az élt A függvény két csomópontot fogad el paraméterként, és megkeresi a második (szomszéd) csomópont indexét a fő csomópont szomszédok listájában. Ezután eltávolítja a szomszédot csomópont. Szomszédok nevű technika segítségével a szelet felszeletelése.

Az eltávolítás úgy működik, hogy a szelet elemeit a megadott indexig felveszi (de nem tartalmazza), a szelet elemeit pedig a megadott index után, és összefűzi. A megadott indexen lévő elem elhagyása.

Ebben az esetben van egy irányítatlan gráf, ezért az élei kétirányúak. Ezért kellett felhívnia a távolítsa el az élt kétszer főben RemoveEdge függvény segítségével eltávolíthatja a szomszédot a csomópont listájáról, és fordítva.

Csomópont eltávolítása a grafikonról

Ha el tudja távolítani az éleket, eltávolíthatja a csomópontokat is. Az alábbiakban látható a függvény a csomópontok eltávolítására a grafikonból:

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

A függvény elfogadja annak a csomópontnak az azonosítóját, amelyet el kell távolítania. Ellenőrzi, hogy a csomópont létezik-e, mielőtt eltávolítaná az összes élét. Ezután törli a csomópontot a grafikonról a Go beépített funkciójával töröl funkció.

Dönthet úgy, hogy több módszert is implementál a grafikonhoz, például olyan függvényeket, amelyek a grafikonon a részleges kereséssel vagy a szélességi kereséssel való bejárásra szolgálnak, vagy egy függvényt a grafikon kinyomtatására. Igényei szerint bármikor hozzáadhat metódusokat a struktúrához.

Azt is meg kell jegyezni, hogy a grafikonok nagyon hatékonyak, de ha nem megfelelően használják, tönkretehetik az alkalmazás szerkezetét. Fejlesztőként tudnia kell, hogyan válasszon adatstruktúrákat különböző felhasználási esetekhez.

Építsen optimalizált szoftvert a megfelelő adatstruktúrák használatával

A Go már most is nagyszerű platformot biztosít hatékony szoftveralkalmazások fejlesztéséhez, de ha figyelmen kívül hagyja a jót fejlesztési gyakorlatokat, különböző problémákat okozhat az alkalmazás architektúrájában és teljesítményében.

Az egyik fontos bevált gyakorlat a megfelelő adatszerkezetek, például tömbök, csatolt listák és grafikonok alkalmazása a különböző igényekhez. Ezzel biztosíthatja, hogy az alkalmazás megfelelően működjön, és kevésbé aggódjon a teljesítmény szűk keresztmetszete vagy az esetleges hibák miatt.