Как реализовать структуру данных графа в Golang

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

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

Так что же такое график? Как реализовать графы в Go?

Что такое графики и диаграммы?

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

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

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

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

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

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

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

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

Следующий код иллюстрирует структуру Node:

тип Node struct {Соседи ()*Узел}

Учебное внимание будет сосредоточено на неориентированной диаграмме. Однако для ясности вот конструкция Node для ориентированных графов:

type Node struct { OutNeighbors ()*Node // исходящие ребра InNeighbors ()*Node // входящие ребра }

При таком определении срез OutNeighbors будет содержать узлы, ребра которых идут от текущего узла, а срез InNeighbors будет содержать узел, ребра которого ведут к текущему узлу.

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

Следующий код покажет структуру Graph:

тип Graph struct { карта узлов (int) * Node }

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

Вам нужна функция, которая действует как новый конструктор графа. Это выделит память для непрерывного списка, а также позволит вам добавлять узлы в граф. Код ниже определяет конструктор для класса Graph:

func NewGraph() *Graph { return &Graph{узлы: make(map(int)*Node), } }

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

Добавьте узлы на график

Вам нужна функция вставки, как это:

func (g *Graph) AddNode(nodeID int) { если _ существует := g.nodes(nodeID); !exists { newNode := &Node{ Соседи: ()*Node{}, } g.nodes(ID узла) = newNode fmt.Println(“Новый узел добавлен в граф”) } else { fmt.Println(“Узел уже существует! “) } }

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

Добавить край к диаграмме

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

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

Добавление ребра в неориентированный граф — это просто процесс создания двух соседних узлов. Эта функция берет оба узла по переданному ей ID и соединяет их со слайсом Neighbours друг друга.

Удалить ребро из графика

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

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

Вот реализация функции removeEdge:

func (g *Graph) removeEdge(узел, сосед *Узел) { индекс := -1 для i, n := диапазон node.Neighbors { if n == сосед { index = i break } } if index != -1 { node.Neighbors = append(node.Neighbors(:index), node.Neighbors(index+1:).) } } func (g *Graph) RemoveEdge(узел, сосед *Node) { g.removeEdge(узел, сосед) g.removeEdge(сосед, узел) fmt.Println(“Ребро успешно удалено”) }

Функция removeEdge принимает два узла в качестве параметров и находит индекс второго узла в списке соседей основного узла. Затем он продолжает удалять соседей из node.Neighbors, используя технику среза имени.

Исключение работает, беря элементы среза (но не включая) до определенного индекса, элементы среза после указанного индекса и объединяя их. Оставьте указанный индекс элемента.

В этом случае у вас есть неориентированный граф, поэтому его ребро двумерно. Вот почему вы должны дважды вызвать removeEdge в основной функции RemoveEdge, чтобы удалить соседа из списка узла, и наоборот.

Удалить узел из графика

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

func (g *Graph) RemoveNode(nodeID int) { узел, существует := g.nodes(nodeID) if !exists { fmt.Println(“Узел не существует”) return } для _, сосед := узел диапазона. Neighbours { g.RemoveEdge(узел, сосед) } delete(g.nodes, nodeID) fmt.Println(“Узел успешно удален”) }

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

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