Графиките са една от най-важните структури от данни, които трябва да знаете като програмист. Научете как да го внедрите в Golang.
Проблеми, свързани с графики, често ще се сблъскват в софтуерната индустрия. Независимо дали при технически интервюта или при изграждане на приложения, които използват графики.
Графиките са основни структури от данни, използвани в различни приложения, вариращи от социални мрежи и транспортни системи до двигатели за препоръки и анализ на мрежата.
Какво е графика и как можете да внедрите графики в Go?
Какво е графика?
Графът е нелинейна структура от данни, която представлява колекция от възли (или върхове) и връзки между тях (ръбове). Графиките се използват широко в софтуерни приложения, които се занимават основно с връзки като компютърни мрежи, социални мрежи и др.
Графиката е една от структурите от данни, които трябва да знаете като програмист. Графиките предоставят мощен и гъвкав начин за моделиране и анализиране на различни сценарии от реалния свят и това ги прави основна и основна структура от данни в компютърните науки.
Голямо разнообразие от алгоритми за решаване на проблеми, използвани в света на софтуера, се основават на графики. Можете да се гмурнете по-дълбоко в графиките в това ръководство за структурата на данните на графиката.
Внедряване на графика в Golang
Повечето пъти, за да внедрите структура от данни сами, трябва да внедрите обектно-ориентирано програмиране (ООП) концепции, но внедряване на ООП в Go не е точно същият, какъвто го имате в други езици като Java и C++.
Go използва структури, типове и интерфейси за внедряване на OOP концепции и това е всичко, от което се нуждаете, за да внедрите графична структура от данни и нейните методи.
Графът се състои от възли (или върхове) и ръбове. Възелът е обект или елемент в графиката. Пример за възел е устройство в мрежа или човек в социална мрежа. Докато ръбът е връзка или връзка между два възела.
За да реализирате графика в Go, първо трябва да дефинирате структура на възел, чието свойство ще бъде нейните съседи. Съседите на възел са другите възли, които са директно свързани с възела.
В насочените графи ръбовете имат посоки, така че само възлите, към които сочи даден възел, се считат за негови съседи. Докато в неориентираните графи всички възли, които споделят ребро с възел, са негови съседи.
Следният код демонстрира как Възел структура изглежда:
type Node struct {
Neighbors []*Node
}
В тази статия фокусът ще бъде върху неориентирана графика. Въпреки това, за да осигурим по-голяма яснота, ето какво a Възел структурата за насочена графа може да изглежда така:
type Node struct {
OutNeighbors []*Node // outgoing edges
InNeighbors []*Node // incoming edges
}
С това определение, OutNeighbors slice ще съхранява възлите, към които има изходящи ръбове от текущия възел, и В съседи slice ще съхранява възлите, от които има входящи ръбове към текущия възел.
Ще внедрите графиката, като използвате карта на цели числа към възли. Тази карта служи като списък на съседство (обичайният начин за представяне на графики). Ключът служи като уникален идентификатор за възел, докато стойността ще бъде възелът.
Следният код показва Графика структура:
type Graph struct {
nodes map[int]*Node
}
Целият ключ може също да си представим като стойността на възела, към който е картографиран. Въпреки че в сценарии от реалния свят вашият възел може да бъде различна структура от данни, представляваща профил на човек или нещо подобно. В такива случаи трябва да имате данните като едно от свойствата на структурата 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!")
}
}
The AddNode функцията добавя нов възел в графиката с ID, предадено му като параметър. Функцията проверява дали вече съществува възел със същия идентификатор, преди да го добави към графиката.
Добавяне на ръб към графиката
Следващият важен метод на структурата на данните на графиката е функцията за добавяне на ребро (т.е. за създаване на връзка между два възела). Тъй като графиката тук е неориентирана, няма нужда да се притеснявате за посоката, когато създавате ръбове.
Ето функцията за добавяне на ребро между два възела на графиката:
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)
}
Доста просто! Добавянето на ръбове в неориентирана графа е просто процес на превръщане на двата възела в съседни един на друг. Функцията получава и двата възела чрез идентификаторите, предадени й, и ги добавя един към друг Съседи парче.
Премахване на ребро от графиката
За да премахнете възел от графика, трябва да го премахнете от всички списъци на съседите му, за да сте сигурни, че няма несъответствия в данните.
Процесът на премахване на възел от всички негови съседи е същият като процеса на премахване на ръбове (или счупване връзки) между възлите, следователно първо трябва да дефинирате функцията за премахване на ръбове, преди да дефинирате тази, която да премахване на възли.
По-долу е изпълнението на removeEdge функция:
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 функцията приема два възела като параметри и търси индекса на втория (съседен) възел в списъка със съседи на основния възел. След това продължава, за да премахне съседа от възел. Съседи с помощта на техника, наречена нарязване на филийката.
Премахването работи, като взема елементите на среза до (но не включително) посочения индекс и елементи на среза след посочения индекс и ги свързва. Оставяне на елемента с посочения индекс.
В този случай имате неориентиран график, следователно неговите ръбове са двупосочни. Ето защо трябваше да се обадите на removeEdge два пъти основно RemoveEdge функция за премахване на съседа от списъка на възела и обратно.
Премахване на възел от графиката
След като сте в състояние да премахнете ръбове, можете също да премахнете възли. По-долу е функцията за премахване на възли от графиката:
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")
}
Функцията приема идентификатора на възела, който трябва да премахнете. Той проверява дали възелът съществува, преди да продължи да премахва всичките му ръбове. След това изтрива възела от графиката с помощта на вградения Go Изтрий функция.
Можете да изберете да приложите повече методи за вашата графика, като например функции за обхождане на графиката с помощта на търсене първо в дълбочина или първо търсене в ширина, или функция за отпечатване на графиката. Винаги можете да добавяте методи към структурата според вашите нужди.
Трябва също така да имате предвид, че графиките са много ефективни, но ако не се използват правилно, могат да разрушат структурата на вашето приложение. Трябва да знаете как да избирате структури от данни за различни случаи на употреба като разработчик.
Създайте оптимизиран софтуер, като използвате правилните структури от данни
Go вече предоставя страхотна платформа за разработване на ефективни софтуерни приложения, но когато пренебрегнете добрата практики за разработка, това може да причини различни проблеми за архитектурата и производителността на вашето приложение.
Една важна най-добра практика е приемането на правилните структури от данни като масиви, свързани списъци и графики за различни нужди. С това можете да се уверите, че вашето приложение работи правилно и да се тревожите по-малко за проблеми с производителността или повреди, които могат да възникнат.