Como implementar a estrutura de dados do gráfico em Golang

Problemas relacionados a gráficos geralmente surgem na indústria de software. Seja em entrevistas técnicas ou na construção de aplicações que fazem uso de gráficos.

Os gráficos são estruturas de dados fundamentais usadas em várias aplicações, desde redes sociais e sistemas de transporte até mecanismos de recomendação e análise de rede.

O que é um gráfico e como você pode implementar gráficos em Go?

O que é um gráfico?

Um grafo é uma estrutura de dados não linear que representa uma coleção de nós (ou vértices) e conexões entre eles (arestas). Os gráficos são amplamente usados ​​em aplicativos de software que lidam fortemente com conexões como redes de computadores, redes sociais e muito mais.

Um gráfico é um dos as estruturas de dados que você deve saber como programador. Os gráficos fornecem uma maneira poderosa e flexível de modelar e analisar vários cenários do mundo real, e isso os torna uma estrutura de dados fundamental e central na ciência da computação.

Uma grande variedade de algoritmos de solução de problemas usados ​​no mundo do software são baseados em gráficos. Você pode mergulhar mais fundo nos gráficos neste guia para a estrutura de dados do gráfico.

Implementando um gráfico em Golang

Na maioria das vezes, para implementar uma estrutura de dados sozinho, você precisa implementar Programação Orientada a Objetos (POO) conceitos, mas implementando OOP em Go não é exatamente o mesmo que você tem em outras linguagens como Java e C++.

Go usa structs, tipos e interfaces para implementar conceitos OOP, e isso é tudo que você precisa para implementar uma estrutura de dados grafos e seus métodos.

Um grafo consiste em nós (ou vértices) e arestas. Um nó é uma entidade ou elemento no grafo. Um exemplo de nó é um dispositivo em uma rede ou uma pessoa em uma rede social. Enquanto uma borda é uma conexão ou relacionamento entre dois nós.

Para implementar um grafo em Go, primeiro você precisa definir um node struct cuja propriedade será seus vizinhos. Os vizinhos de um nó são os outros nós que estão diretamente conectados ao nó.

Em grafos direcionados, as arestas têm direções, de modo que apenas os nós para os quais um determinado nó aponta são considerados seus vizinhos. Enquanto em grafos não direcionados, todos os nós que compartilham uma aresta com um nó são seus vizinhos.

O código a seguir demonstra como o Nó aparência da estrutura:

type Node struct {
 Neighbors []*Node
}

Neste artigo, o foco estará em um grafo não direcionado. No entanto, para fornecer melhor clareza, aqui está o que um Nó struct para um grafo direcionado pode se parecer com:

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

Com essa definição, o Vizinhos externos fatia irá armazenar os nós para os quais existem arestas de saída do nó atual, e o Em vizinhos slice armazenará os nós dos quais há arestas de entrada para o nó atual.

Você implementará o gráfico usando um mapa de números inteiros para nós. Este mapa serve como lista de adjacência (a forma comum de representar gráficos). A chave serve como um ID exclusivo para um nó, enquanto o valor será o nó.

O código a seguir mostra o Gráfico estrutura:

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

A chave inteira também pode ser imaginada como o valor do nó para o qual está mapeada. Embora em cenários do mundo real, seu nó possa ser uma estrutura de dados diferente representando o perfil de uma pessoa ou algo semelhante. Nesses casos, você deve ter os dados como uma das propriedades da estrutura do nó.

Você precisa de uma função para atuar como um construtor para inicializar um novo gráfico. Isso alocará memória para a lista de adjacência e permitirá adicionar nós ao gráfico. O código abaixo é a definição de um construtor para o Gráfico aula:

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

Agora você pode definir métodos para executar vários tipos de operações no gráfico. Existem várias operações que você pode executar em um gráfico, desde a adição de nós até a criação de arestas entre os nós, pesquisa de nós e muito mais.

Neste artigo, você explorará as funções para adicionar nós e arestas a gráficos, bem como removê-los. As ilustrações de código a seguir são as implementações das funções para executar essas operações.

Adicionando um nó ao gráfico

Para adicionar um novo nó ao gráfico, você precisa da função de inserção que se parece com esta:

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

O AddNode A função adiciona um novo nó no gráfico com o ID passado a ele como um parâmetro. A função verifica se já existe um nó com o mesmo ID antes de adicioná-lo ao gráfico.

Adicionando uma aresta ao gráfico

O próximo método importante da estrutura de dados do grafo é a função para adicionar uma aresta (isto é, para criar uma conexão entre dois nós). Como o gráfico aqui é não direcionado, não há necessidade de se preocupar com a direção ao criar arestas.

Aqui está a função para adicionar uma aresta entre dois nós no 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)
}

Bem simples! A adição de arestas em um grafo não direcionado é simplesmente o processo de tornar ambos os nós vizinhos um do outro. A função obtém ambos os nós pelos IDs passados ​​para ela e anexa ambos um ao outro. Vizinhos fatiar.

Removendo uma aresta do gráfico

Para remover um nó de um grafo, você precisa removê-lo de todas as listas de seus vizinhos para garantir que não haja inconsistências de dados.

O processo de remover um nó de todos os seus vizinhos é o mesmo que remover arestas (ou quebrar conexões) entre os nós, portanto, você deve definir a função para remover arestas primeiro antes de definir aquela para remover nós.

Abaixo está a implementação do removeEdge função:

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

O removeEdge A função aceita dois nós como parâmetros e procura o índice do segundo nó (vizinho) na lista de vizinhos do nó principal. Em seguida, segue em frente para remover o vizinho de nó. Vizinhos usando uma técnica chamada cortando a fatia.

A remoção funciona levando os elementos da fatia até (mas não incluindo) o índice especificado e os elementos da fatia após o índice especificado e concatenando-os. Deixando o elemento no índice especificado fora.

Neste caso, você tem um grafo não direcionado, portanto suas arestas são bidirecionais. É por isso que você teve que ligar para o removeEdge duas vezes no principal RemoveEdge função para remover o vizinho da lista de nós e vice-versa.

Removendo um nó do gráfico

Depois de remover arestas, você também pode remover nós. Abaixo está a função para remover nós do grafo:

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

A função aceita o ID do nó que você precisa remover. Ele verifica se o nó existe antes de remover todas as suas arestas. Em seguida, ele exclui o nó do grafo usando o recurso embutido do Go excluir função.

Você pode optar por implementar mais métodos para seu gráfico, como funções para percorrer o gráfico usando pesquisa em profundidade ou pesquisa em largura, ou uma função para imprimir o gráfico. Você sempre pode adicionar métodos à estrutura de acordo com suas necessidades.

Você também deve observar que os gráficos são muito eficientes, mas se não forem usados ​​corretamente, podem arruinar a estrutura do seu aplicativo. Você deve saber como escolher estruturas de dados para diferentes casos de uso como desenvolvedor.

Crie um software otimizado usando as estruturas de dados corretas

Go já fornece uma ótima plataforma para desenvolver aplicativos de software eficientes, mas quando você negligencia bons práticas de desenvolvimento, pode causar diversos problemas para a arquitetura e performance de sua aplicação.

Uma prática recomendada importante é adotar as estruturas de dados corretas, como matrizes, listas encadeadas e gráficos, para diferentes necessidades. Com isso, você pode garantir que seu aplicativo esteja funcionando corretamente e se preocupar menos com gargalos de desempenho ou falhas que possam surgir.