Како имплементирати структуру података графикона у Голангу

Проблеми у вези са графовима често ће вам се појавити у софтверској индустрији. Било на техничким интервјуима или приликом израде апликација које користе графиконе.

Графови су основне структуре података које се користе у различитим апликацијама, у распону од друштвених мрежа и транспортних система до механизама за препоруке и анализе мреже.

Шта је граф и како можете да примените графиконе у Го?

Шта је граф?

Граф је нелинеарна структура података која представља колекцију чворова (или врхова) и веза између њих (ивица). Графови се широко користе у софтверским апликацијама које се у великој мери баве везама као што су рачунарске мреже, друштвене мреже и још много тога.

Графикон је један од структуре података које треба да знате као програмер. Графови пружају моћан и флексибилан начин за моделирање и анализу различитих сценарија из стварног света, а то их чини фундаменталном и основном структуром података у рачунарској науци.

Велики избор алгоритама за решавање проблема који се користе у свету софтвера засновани су на графовима. У овоме можете дубље заронити у графиконе водич за структуру података графикона.

Имплементација графикона у Голангу

У већини случајева да бисте сами имплементирали структуру података, морате је имплементирати објектно оријентисано програмирање (ООП) концепти, али имплементација ООП-а у Го није потпуно исти као што га имате у другим језицима као што су Јава и Ц++.

Го користи структуре, типове и интерфејсе за имплементацију ООП концепата, а ово је све што вам је потребно за имплементацију структуре података графикона и њених метода.

Граф се састоји од чворова (или врхова) и ивица. Чвор је ентитет или елемент у графу. Пример чвора је уређај на мрежи или особа на друштвеној мрежи. Док је ивица веза или однос између два чвора.

Да бисте имплементирали граф у Го, прво морате да дефинишете структуру чвора чије ће својство бити њени суседи. Суседи чвора су остали чворови који су директно повезани са чвором.

У усмереним графовима, ивице имају правце тако да се само чворови на које дати чвор указује сматрају његовим суседима. Док су у неусмереним графовима, сви чворови који деле ивицу са чвором су његови суседи.

Следећи код показује како Чвор структура изгледа:

type Node struct {
 Neighbors []*Node
}

У овом чланку фокус ће бити на неусмереном графу. Међутим, ради боље јасноће, ево шта а Чвор структура за усмерени граф може изгледати овако:

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

Са овом дефиницијом, ОутНеигхбоурс слице ће ускладиштити чворове до којих постоје одлазеће ивице из тренутног чвора, и ИнНеигхбоурс слице ће ускладиштити чворове из којих долазе долазне ивице у тренутни чвор.

Графикон ћете имплементирати користећи мапу целих бројева у чворове. Ова мапа служи као листа суседности (уобичајени начин представљања графова). Кључ служи као јединствени ИД за чвор, док ће вредност бити чвор.

Следећи код показује Граф структура:

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

Целобројни кључ се такође може замислити као вредност чвора на који је мапиран. Иако у сценаријима из стварног света, ваш чвор може бити другачија структура података која представља профил особе или нешто слично. У таквим случајевима, требало би да имате податке као једно од својстава структуре чвора.

Потребна вам је функција која ће деловати као конструктор за иницијализацију новог графикона. Ово ће доделити меморију за листу суседности и омогућити вам да додате чворове на граф. Код испод је дефиниција конструктора за Граф класа:

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

Сада можете дефинисати методе за извођење различитих врста операција на графикону. Постоје различите операције које можете извршити на графу, од додавања чворова до креирања ивица између чворова, тражења чворова и још много тога.

У овом чланку ћете истражити функције за додавање чворова и ивица графовима, као и њихово уклањање. Следеће илустрације кода су имплементације функција за извођење ових операција.

Додавање чвора на графикон

Да бисте додали нови чвор на графикон, потребна вам је функција уметања која изгледа овако:

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

Тхе АддНоде функција додаје нови чвор на граф са ИД-ом који му је прослеђен као параметар. Функција проверава да ли чвор са истим ИД-ом већ постоји пре него што га дода на графикон.

Додавање ивице графикону

Следећи важан метод структуре података графа је функција за додавање ивице (тј. за стварање везе између два чвора). Пошто је граф овде неусмерен, нема потребе да бринете о правцу приликом креирања ивица.

Ево функције за додавање ивице између два чвора на графу:

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

Прилично једноставно! Додавање ивица у неусмереном графу је једноставно процес прављења оба чвора суседима један другом. Функција добија оба чвора помоћу ИД-ова који су јој прослеђени и додаје их један другом комшије кришка.

Уклањање ивице са графикона

Да бисте уклонили чвор са графикона, потребно је да га уклоните са свих листа његових суседа како бисте били сигурни да нема недоследности података.

Процес уклањања чвора из свих његових суседа је исти као и процес уклањања ивица (или разбијања везе) између чворова, стога морате прво дефинисати функцију за уклањање ивица пре него што дефинишете ону за уклонити чворове.

Испод је имплементација ремовеЕдге функција:

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

Тхе ремовеЕдге функција прихвата два чвора као параметре и тражи индекс другог (суседног) чвора на листи суседа главног чвора. Затим се наставља уклањање комшије чвор. комшије користећи технику тзв резање кришке.

Уклањање функционише тако што се елементи исечка узимају до (али не укључујући) наведени индекс, а елементи пресека после наведеног индекса и спајају их. Остављајући елемент на наведеном индексу.

У овом случају имате неусмерени граф, па су његове ивице двосмерне. Због тога сте морали да позовете ремовеЕдге два пута у главном РемовеЕдге функција за уклањање суседа са листе чворова и обрнуто.

Уклањање чвора са графикона

Када будете у могућности да уклоните ивице, можете уклонити и чворове. Испод је функција за уклањање чворова са графикона:

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

Функција прихвата ИД чвора који треба да уклоните. Проверава да ли чвор постоји пре него што уклони све његове ивице. Затим брише чвор са графа користећи уграђени Го избрисати функција.

Можете изабрати да примените више метода за свој граф, као што су функције за прелазак преко графа користећи претрагу у правцу прве или у ширину, или функцију за штампање графикона. Увек можете додати методе у структуру према вашим потребама.

Такође треба да приметите да су графикони веома ефикасни, али ако се не користе правилно, могу да униште структуру ваше апликације. Морате знати како одабрати структуре података за различите случајеве употребе као програмер.

Направите оптимизован софтвер користећи праве структуре података

Го већ пружа одличну платформу за развој ефикасних софтверских апликација, али када занемарите добро развојне праксе, може изазвати различите проблеме за архитектуру и перформансе ваше апликације.

Једна важна најбоља пракса је усвајање правих структура података као што су низови, повезане листе и графикони, за различите потребе. На овај начин можете осигурати да ваша апликација ради исправно и мање бринути о уским грлима у перформансама или кваровима који се могу појавити.