Comment implémenter la structure de données graphique dans Golang

Les problèmes liés aux graphes se présenteront souvent dans l'industrie du logiciel. Que ce soit lors d'entretiens techniques ou lors de la création d'applications utilisant des graphiques.

Les graphes sont des structures de données fondamentales utilisées dans diverses applications, allant des réseaux sociaux et des systèmes de transport aux moteurs de recommandation et à l'analyse de réseau.

Qu'est-ce qu'un graphique et comment pouvez-vous implémenter des graphiques dans Go ?

Qu'est-ce qu'un graphique?

Un graphe est une structure de données non linéaire qui représente une collection de nœuds (ou sommets) et des connexions entre eux (arêtes). Les graphiques sont largement utilisés dans les applications logicielles qui traitent fortement des connexions telles que les réseaux informatiques, les réseaux sociaux, etc.

Un graphique est l'un des

les structures de données que vous devez connaître en tant que programmeur. Les graphiques offrent un moyen puissant et flexible de modéliser et d'analyser divers scénarios du monde réel, ce qui en fait une structure de données fondamentale et essentielle en informatique.

Une grande variété d'algorithmes de résolution de problèmes utilisés dans le monde du logiciel sont basés sur des graphes. Vous pouvez plonger plus profondément dans les graphiques dans ce guide de la structure des données du graphe.

Implémentation d'un graphique dans Golang

La plupart du temps, pour implémenter une structure de données par vous-même, vous devez implémenter programmation orientée objet (POO) notions, mais mise en œuvre de la POO en Go n'est pas exactement la même que celle que vous avez dans d'autres langages comme Java et C++.

Go utilise des structures, des types et des interfaces pour implémenter des concepts POO, et ce sont tout ce dont vous avez besoin pour implémenter une structure de données graphique et ses méthodes.

Un graphe est constitué de nœuds (ou sommets) et d'arêtes. Un nœud est une entité ou un élément du graphe. Un exemple de nœud est un appareil sur un réseau ou une personne sur un réseau social. Alors qu'un bord est une connexion ou une relation entre deux nœuds.

Pour implémenter un graphe dans Go, vous devez d'abord définir une structure de nœud dont la propriété sera ses voisins. Les voisins d'un nœud sont les autres nœuds qui sont directement connectés au nœud.

Dans les graphes orientés, les arêtes ont des directions, de sorte que seuls les nœuds vers lesquels un nœud donné pointe sont considérés comme ses voisins. Alors que dans les graphes non orientés, tous les nœuds qui partagent une arête avec un nœud sont ses voisins.

Le code suivant montre comment le Nœud la structure ressemble à :

type Node struct {
 Neighbors []*Node
}

Dans cet article, l'accent sera mis sur un graphe non orienté. Cependant, pour plus de clarté, voici ce qu'est un Nœud struct pour un graphe orienté pourrait ressembler à :

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

Avec cette définition, le OutVoisins slice stockera les nœuds vers lesquels il y a des bords sortants du nœud actuel, et le Chez les voisins slice stockera les nœuds à partir desquels il y a des arêtes entrantes vers le nœud actuel.

Vous implémenterez le graphique à l'aide d'une carte d'entiers aux nœuds. Cette carte sert de liste de contiguïté (la manière courante de représenter les graphiques). La clé sert d'identifiant unique pour un nœud, tandis que la valeur sera le nœud.

Le code suivant montre le Graphique structure :

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

La clé entière peut également être imaginée comme la valeur du nœud auquel elle est mappée. Bien que dans des scénarios réels, votre nœud pourrait être une structure de données différente représentant le profil d'une personne ou quelque chose de similaire. Dans de tels cas, vous devez avoir les données comme l'une des propriétés de la structure Node.

Vous avez besoin d'une fonction pour agir en tant que constructeur pour initialiser un nouveau graphique. Cela allouera de la mémoire pour la liste de contiguïté et vous permettra d'ajouter des nœuds au graphique. Le code ci-dessous est la définition d'un constructeur pour le Graphique classe:

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

Vous pouvez maintenant définir des méthodes pour effectuer divers types d'opérations sur le graphique. Il existe diverses opérations que vous pouvez effectuer sur un graphique, de l'ajout de nœuds à la création d'arêtes entre les nœuds, la recherche de nœuds, etc.

Dans cet article, vous explorerez les fonctions permettant d'ajouter des nœuds et des arêtes aux graphiques, ainsi que de les supprimer. Les illustrations de code suivantes sont les implémentations des fonctions permettant d'effectuer ces opérations.

Ajout d'un nœud au graphe

Pour ajouter un nouveau nœud au graphique, vous avez besoin de la fonction d'insertion qui ressemble à ceci :

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

Le AjouterNoeud La fonction ajoute un nouveau nœud sur le graphique avec l'ID qui lui est passé en tant que paramètre. La fonction vérifie si un nœud avec le même ID existe déjà avant de l'ajouter au graphique.

Ajout d'une arête au graphique

La prochaine méthode importante de la structure de données du graphe est la fonction d'ajout d'une arête (c'est-à-dire de création d'une connexion entre deux nœuds). Étant donné que le graphe ici est non orienté, il n'est pas nécessaire de se soucier de la direction lors de la création d'arêtes.

Voici la fonction pour ajouter une arête entre deux nœuds sur le graphe :

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

Assez simple! L'ajout d'arêtes dans un graphe non orienté consiste simplement à rendre les deux nœuds voisins l'un de l'autre. La fonction obtient les deux nœuds par les ID qui lui sont transmis et les ajoute les uns aux autres. Voisins tranche.

Suppression d'une arête du graphique

Pour supprimer un nœud d'un graphique, vous devez le supprimer de toutes les listes de ses voisins pour vous assurer qu'il n'y a pas d'incohérences de données.

Le processus de suppression d'un nœud de tous ses voisins est le même que le processus de suppression des bords (ou de rupture connexions) entre les nœuds, vous devez donc définir la fonction de suppression des arêtes avant de définir celle à supprimer des nœuds.

Ci-dessous la mise en œuvre de la supprimerEdge fonction:

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

Le supprimerEdge La fonction accepte deux nœuds comme paramètres et recherche l'index du deuxième nœud (voisin) dans la liste des voisins du nœud principal. Il va ensuite de l'avant pour retirer le voisin de nœud. Voisins à l'aide d'une technique appelée trancher la tranche.

La suppression fonctionne en prenant les éléments de la tranche jusqu'à (mais sans l'inclure) l'index spécifié, et les éléments de la tranche après l'index spécifié, et en les concaténant. Laissant l'élément à l'index spécifié out.

Dans ce cas, vous avez un graphe non orienté, donc ses arêtes sont bidirectionnelles. C'est pourquoi vous avez dû appeler le supprimerEdge deux fois en gros SupprimerBord fonction pour supprimer le voisin de la liste du nœud et vice-versa.

Suppression d'un nœud du graphe

Une fois que vous êtes en mesure de supprimer des arêtes, vous pouvez également supprimer des nœuds. Voici la fonction pour supprimer les nœuds du graphique :

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 fonction accepte l'ID du nœud que vous devez supprimer. Il vérifie si le nœud existe avant de supprimer tous ses bords. Il supprime ensuite le nœud du graphique à l'aide de Go intégré supprimer fonction.

Vous pouvez choisir d'implémenter plus de méthodes pour votre graphique, telles que des fonctions pour parcourir le graphique à l'aide d'une recherche en profondeur ou d'une recherche en largeur, ou une fonction pour imprimer le graphique. Vous pouvez toujours ajouter des méthodes à la structure en fonction de vos besoins.

Vous devez également noter que les graphiques sont très efficaces mais s'ils ne sont pas utilisés correctement, ils peuvent ruiner la structure de votre application. Vous devez savoir choisir des structures de données pour différents cas d'utilisation en tant que développeur.

Construire un logiciel optimisé en utilisant les bonnes structures de données

Go fournit déjà une excellente plate-forme pour développer des applications logicielles efficaces, mais lorsque vous négligez les bonnes pratiques de développement, cela peut entraîner différents problèmes pour l'architecture et les performances de votre application.

Une bonne pratique importante consiste à adopter les bonnes structures de données telles que les tableaux, les listes chaînées et les graphiques, pour différents besoins. Avec cela, vous pouvez vous assurer que votre application fonctionne correctement et moins vous soucier des goulots d'étranglement ou des pannes de performances qui peuvent survenir.