Cómo implementar la estructura de datos de gráfico en Golang

Los problemas relacionados con gráficos a menudo se presentarán en la industria del software. Ya sea en entrevistas técnicas o al construir aplicaciones que hagan uso de gráficos.

Los gráficos son estructuras de datos fundamentales que se utilizan en diversas aplicaciones, desde redes sociales y sistemas de transporte hasta motores de recomendación y análisis de redes.

¿Qué es un gráfico y cómo puede implementar gráficos en Go?

¿Qué es un gráfico?

Un gráfico es una estructura de datos no lineal que representa una colección de nodos (o vértices) y conexiones entre ellos (aristas). Los gráficos se utilizan ampliamente en aplicaciones de software que se ocupan en gran medida de conexiones como redes informáticas, redes sociales y más.

Un gráfico es uno de las estructuras de datos que debes conocer como programador. Los gráficos proporcionan una forma poderosa y flexible de modelar y analizar varios escenarios del mundo real, y esto los convierte en una estructura de datos fundamental y central en informática.

Una amplia variedad de algoritmos de resolución de problemas utilizados en el mundo del software se basan en gráficos. Puede profundizar más en los gráficos en este guía a la estructura de datos del gráfico.

Implementando un gráfico en Golang

La mayoría de las veces, para implementar una estructura de datos usted mismo, necesita implementar programación orientada a objetos (POO) conceptos, pero implementando programación orientada a objetos en Go no es exactamente igual a como lo tienes en otros lenguajes como Java y C++.

Go usa estructuras, tipos e interfaces para implementar conceptos de programación orientada a objetos, y esto es todo lo que necesita para implementar una estructura de datos de gráfico y sus métodos.

Un gráfico consta de nodos (o vértices) y aristas. Un nodo es una entidad o elemento en el gráfico. Un ejemplo de un nodo es un dispositivo en una red o una persona en una red social. Mientras que un borde es una conexión o relación entre dos nodos.

Para implementar un gráfico en Go, primero debe definir una estructura de nodo cuya propiedad serán sus vecinos. Los vecinos de un nodo son los otros nodos que están directamente conectados al nodo.

En los gráficos dirigidos, los bordes tienen direcciones, por lo que solo los nodos a los que apunta un nodo dado se consideran sus vecinos. Mientras que en gráficos no dirigidos, todos los nodos que comparten un borde con un nodo son sus vecinos.

El siguiente código demuestra cómo el Nodo la estructura se ve:

type Node struct {
 Neighbors []*Node
}

En este artículo, la atención se centrará en un gráfico no dirigido. Sin embargo, para proporcionar una mayor claridad, esto es lo que un Nodo La estructura de un gráfico dirigido podría verse así:

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

Con esta definición, la FueraVecinos slice almacenará los nodos a los que hay bordes salientes desde el nodo actual, y el EnVecinos slice almacenará los nodos desde los cuales hay aristas entrantes al nodo actual.

Implementará el gráfico mediante un mapa de enteros a nodos. Este mapa sirve como lista de adyacencia (la forma común de representar gráficos). La clave sirve como una identificación única para un nodo, mientras que el valor será el nodo.

El siguiente código muestra la Grafico estructura:

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

La clave entera también se puede imaginar como el valor del nodo al que se asigna. Aunque en escenarios del mundo real, su nodo podría ser una estructura de datos diferente que represente el perfil de una persona o algo similar. En tales casos, debe tener los datos como una de las propiedades de la estructura Node.

Necesita una función que actúe como constructor para inicializar un nuevo gráfico. Esto asignará memoria para la lista de adyacencia y le permitirá agregar nodos al gráfico. El siguiente código es la definición de un constructor para el Grafico clase:

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

Ahora puede definir métodos para realizar varios tipos de operaciones en el gráfico. Hay varias operaciones que puede realizar en un gráfico, desde la adición de nodos hasta la creación de bordes entre nodos, la búsqueda de nodos y más.

En este artículo, explorará las funciones para agregar nodos y bordes a los gráficos, así como para eliminarlos. Las siguientes ilustraciones de código son las implementaciones de las funciones para realizar estas operaciones.

Agregar un nodo al gráfico

Para agregar un nuevo nodo al gráfico, necesita la función de inserción que se ve así:

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

El AgregarNodo La función agrega un nuevo nodo en el gráfico con el ID que se le pasa como parámetro. La función verifica si ya existe un nodo con la misma ID antes de agregarlo al gráfico.

Agregar un borde al gráfico

El siguiente método importante de la estructura de datos del gráfico es la función para agregar un borde (es decir, para crear una conexión entre dos nodos). Dado que el gráfico aquí no está dirigido, no hay necesidad de preocuparse por la dirección al crear bordes.

Aquí está la función para agregar un borde entre dos nodos en el gráfico:

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

¡Bastante simple! La adición de aristas en un gráfico no dirigido es simplemente el proceso de hacer que ambos nodos sean vecinos entre sí. La función obtiene ambos nodos por los ID que se le pasan y los agrega entre sí. vecinos rebanada.

Eliminar un borde del gráfico

Para eliminar un nodo de un gráfico, debe eliminarlo de todas las listas de sus vecinos para asegurarse de que no haya inconsistencias en los datos.

El proceso de eliminar un nodo de todos sus vecinos es el mismo que el proceso de eliminar bordes (o romper conexiones) entre los nodos, por lo tanto, primero debe definir la función para eliminar bordes antes de definir el que desea eliminar nodos.

A continuación se muestra la implementación de la eliminarEdge función:

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

El eliminarEdge La función acepta dos nodos como parámetros y busca el índice del segundo nodo (vecino) en la lista de vecinos del nodo principal. Luego continúa para eliminar al vecino de nodo. vecinos usando una técnica llamada cortando la rebanada.

La eliminación funciona tomando los elementos del segmento hasta (pero sin incluir) el índice especificado y los elementos del segmento después del índice especificado y concatenándolos. Dejando fuera el elemento en el índice especificado.

En este caso, tiene un gráfico no dirigido, por lo tanto, sus bordes son bidireccionales. Por eso tuviste que llamar al eliminarEdge dos veces en la principal QuitarBorde función para eliminar al vecino de la lista del nodo y viceversa.

Quitar un nodo del gráfico

Una vez que pueda eliminar bordes, también puede eliminar nodos. A continuación se muestra la función para eliminar nodos del gráfico:

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

La función acepta la ID del nodo que necesita eliminar. Comprueba si el nodo existe antes de eliminar todos sus bordes. A continuación, elimina el nodo del gráfico utilizando el integrado de Go borrar función.

Puede optar por implementar más métodos para su gráfico, como funciones para recorrer el gráfico utilizando la búsqueda primero en sección o la búsqueda primero en anchura, o una función para imprimir el gráfico. Siempre puede agregar métodos a la estructura según sus necesidades.

También debe tener en cuenta que los gráficos son muy eficientes, pero si no se usan correctamente, pueden arruinar la estructura de su aplicación. Debe saber cómo elegir estructuras de datos para diferentes casos de uso como desarrollador.

Cree software optimizado utilizando las estructuras de datos correctas

Go ya proporciona una gran plataforma para desarrollar aplicaciones de software eficientes, pero cuando se descuida la buena prácticas de desarrollo, puede causar diferentes problemas para la arquitectura y el rendimiento de su aplicación.

Una práctica recomendada importante es adoptar las estructuras de datos correctas, como matrices, listas vinculadas y gráficos, para diferentes necesidades. Con esto, puede asegurarse de que su aplicación funcione correctamente y preocuparse menos por los cuellos de botella en el rendimiento o las fallas que puedan surgir.