Графики — одна из самых важных структур данных, которую вы должны знать как программист. Узнайте, как реализовать это в Golang.

Проблемы, связанные с графами, часто возникают в индустрии программного обеспечения. Будь то технические собеседования или создание приложений, использующих графики.

Графики — это фундаментальные структуры данных, используемые в различных приложениях, начиная от социальных сетей и транспортных систем и заканчивая механизмами рекомендаций и сетевым анализом.

Что такое граф и как реализовать графы в Go?

Что такое график?

Граф — это нелинейная структура данных, представляющая набор узлов (или вершин) и связей между ними (ребер). Графики широко используются в программных приложениях, которые активно работают с соединениями, такими как компьютерные сети, социальные сети и т. д.

Граф является одним из структуры данных, которые вы должны знать как программист. Графики предоставляют мощный и гибкий способ моделирования и анализа различных сценариев реального мира, что делает их фундаментальной и основной структурой данных в информатике.

instagram viewer

Большое разнообразие алгоритмов решения задач, используемых в мире программного обеспечения, основано на графах. Вы можете глубже погрузиться в графики в этом руководство по структуре данных графа.

Реализация графика в Golang

В большинстве случаев, чтобы реализовать структуру данных самостоятельно, вам необходимо реализовать объектно-ориентированное программирование (ООП) концепции, но реализация ООП в Go не совсем то же самое, что и в других языках, таких как Java и C++.

Go использует структуры, типы и интерфейсы для реализации концепций ООП, и это все, что вам нужно для реализации структуры данных графа и ее методов.

Граф состоит из узлов (или вершин) и ребер. Узел — это сущность или элемент графа. Примером узла является устройство в сети или человек в социальной сети. В то время как ребро — это соединение или отношение между двумя узлами.

Чтобы реализовать граф в Go, вам сначала нужно определить структуру узла, свойством которой будут его соседи. Соседями узла являются другие узлы, которые непосредственно связаны с узлом.

В ориентированных графах ребра имеют направления, поэтому его соседями считаются только узлы, на которые указывает данный узел. В то время как в неориентированных графах все узлы, которые имеют общее ребро с узлом, являются его соседями.

Следующий код демонстрирует, как Узел структура выглядит:

type Node struct {
 Neighbors []*Node
}

В этой статье основное внимание будет уделено неориентированному графу. Однако, для большей ясности, вот что Узел структура ориентированного графа может выглядеть так:

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

С этим определением Соседи 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!")
 }
}

Добавить узел Функция добавляет новый узел на граф с идентификатором, переданным ему в качестве параметра. Функция проверяет, существует ли узел с таким же идентификатором, прежде чем добавить его в граф.

Добавление ребра к графику

Следующим важным методом структуры данных графа является функция добавления ребра (то есть создания связи между двумя узлами). Поскольку граф здесь неориентированный, нет необходимости беспокоиться о направлении при создании ребер.

Вот функция для добавления ребра между двумя узлами на графике:

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

Функция принимает идентификатор узла, который необходимо удалить. Он проверяет, существует ли узел, прежде чем удалить все его ребра. Затем он удаляет узел из графа, используя встроенный в Go удалить функция.

Вы можете реализовать больше методов для своего графа, например, функции для обхода графа с использованием поиска в глубину или в ширину или функцию для печати графа. Вы всегда можете добавить методы в структуру в соответствии с вашими потребностями.

Вы также должны отметить, что графы очень эффективны, но при неправильном использовании могут разрушить структуру вашего приложения. Вы как разработчик должны знать, как выбирать структуры данных для различных вариантов использования.

Создавайте оптимизированное программное обеспечение, используя правильные структуры данных

Go уже предоставляет отличную платформу для разработки эффективных программных приложений, но когда вы пренебрегаете хорошим практики разработки, это может вызвать различные проблемы с архитектурой и производительностью вашего приложения.

Одним из важных передовых методов является использование правильных структур данных, таких как массивы, связанные списки и графики, для различных нужд. Благодаря этому вы можете убедиться, что ваше приложение работает правильно, и меньше беспокоиться о узких местах производительности или сбоях, которые могут возникнуть.