Последнее обновление 31.08.2023 — Василий Иванов
Проблемы, связанные с графами, часто встречаются в индустрии программного обеспечения. Будь то технические интервью или создание приложений, использующих графики.
Графы — это фундаментальные структуры данных, используемые в различных приложениях, от социальных сетей и транспортных систем до механизмов рекомендаций и сетевого анализа.
Что такое граф и как реализовать графы в Go?
Что такое граф?
Граф — это нелинейная структура данных, представляющая собой совокупность узлов (или вершин) и связей между ними (ребер). Графы широко используются в программных приложениях, которые активно работают с соединениями, такими как компьютерные сети, социальные сети и т. д.
Граф — это одна из структур данных, которую вы должны знать как программист. Графы предоставляют мощный и гибкий способ моделирования и анализа различных сценариев реального мира, что делает их фундаментальной и основной структурой данных в информатике.
На графах основано множество алгоритмов решения задач, используемых в мире программного обеспечения. Вы можете более подробно изучить графики в этом руководстве по структуре данных графа.
Реализация графика в Golang
В большинстве случаев, чтобы реализовать структуру данных самостоятельно, вам необходимо реализовать концепции объектно-ориентированного программирования (ООП), но реализация ООП в Go не совсем такая же, как в других языках, таких как Java и C++.
Go использует структуры, типы и интерфейсы для реализации концепций ООП, и это все, что вам нужно для реализации структуры данных графа и ее методов.
Граф состоит из узлов (или вершин) и ребер. Узел — это сущность или элемент графа. Примером узла является устройство в сети или человек в социальной сети. В то время как ребро — это соединение или взаимосвязь между двумя узлами.
Чтобы реализовать граф в Go, сначала необходимо определить структуру узла, свойством которой будут ее соседи. Соседи узла — это другие узлы, напрямую связанные с ним.
В ориентированных графах ребра имеют направления, поэтому только те узлы, на которые указывает данный узел, считаются его соседями. В неориентированных графах все узлы, имеющие общее ребро с узлом, являются его соседями.
Следующий код демонстрирует, как выглядит структура Node:
type Node struct {
Neighbors []*Node
}
В этой статье основное внимание будет уделено неориентированному графу. Однако для большей ясности вот как может выглядеть структура Node для ориентированного графа:
type Node struct {
OutNeighbors []*Node // outgoing edges
InNeighbors []*Node // incoming edges
}
При таком определении срез OutNeighbors будет хранить узлы, к которым есть исходящие ребра из текущего узла, а срез InNeighbors будет хранить узлы, из которых есть входящие ребра в текущий узел.
Вы реализуете график, используя карту целых чисел с узлами. Эта карта служит списком смежности (обычный способ представления графов). Ключ служит уникальным идентификатором узла, а значением будет узел.
Следующий код показывает структуру Graph:
type Graph struct {
nodes map[int]*Node
}
Целочисленный ключ также можно представить как значение узла, которому он сопоставлен. Хотя в реальных сценариях ваш узел может представлять собой другую структуру данных, представляющую профиль человека или что-то подобное. В таких случаях данные должны быть одним из свойств структуры Node.
Вам нужна функция, которая будет выступать в качестве конструктора для инициализации нового графа. Это выделит память для списка смежности и позволит вам добавлять узлы в граф. Код ниже представляет собой определение конструктора класса Graph:
func NewGraph() *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!")
}
}
Функция AddNode добавляет на граф новый узел с идентификатором, передаваемым ему в качестве параметра. Функция проверяет, существует ли уже узел с таким идентификатором, прежде чем добавлять его в граф.
Добавление ребра к графику
Следующий важный метод структуры данных графа — это функция добавления ребра (то есть создания соединения между двумя узлами). Поскольку граф здесь неориентированный, при создании ребер не нужно беспокоиться о направлении.
Вот функция для добавления ребра между двумя узлами на графике:
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")
}
Функция RemoveEdge принимает два узла в качестве параметров и ищет индекс второго (соседнего) узла в списке соседей основного узла. Затем он удаляет соседа из node.Neighbours, используя технику, называемую нарезкой среза.
Удаление осуществляется путем взятия элементов среза до указанного индекса (но не включая его), а также элементов среза после указанного индекса и их объединения. Оставление элемента по указанному индексу.
В данном случае у вас неориентированный граф, поэтому его ребра двунаправленные. Вот почему вам пришлось дважды вызывать функцию 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 уже предоставляет отличную платформу для разработки эффективных программных приложений, но если вы пренебрегаете хорошими практиками разработки, это может вызвать различные проблемы с архитектурой и производительностью вашего приложения.
Одним из важных передовых методов является использование правильных структур данных, таких как массивы, связанные списки и графики, для различных нужд. Благодаря этому вы можете быть уверены, что ваше приложение работает правильно, и меньше беспокоиться об узких местах производительности или сбоях, которые могут возникнуть.
