So implementieren Sie die Diagrammdatenstruktur in Golang

In der Softwarebranche werden Sie häufig mit graphbezogenen Problemen konfrontiert. Ob in technischen Interviews oder beim Erstellen von Anwendungen, die Diagramme nutzen.

Diagramme sind grundlegende Datenstrukturen, die in verschiedenen Anwendungen verwendet werden, von sozialen Netzwerken und Transportsystemen bis hin zu Empfehlungsmaschinen und Netzwerkanalysen.

Was ist ein Diagramm und wie können Sie Diagramme in Go implementieren?

Was ist ein Diagramm?

Ein Graph ist eine nichtlineare Datenstruktur, die eine Sammlung von Knoten (oder Eckpunkten) und Verbindungen zwischen ihnen (Kanten) darstellt. Diagramme werden häufig in Softwareanwendungen verwendet, die sich stark mit Verbindungen wie Computernetzwerken, sozialen Netzwerken und mehr befassen.

Ein Diagramm ist eines davon die Datenstrukturen, die Sie kennen sollten als Programmierer. Diagramme bieten eine leistungsstarke und flexible Möglichkeit, verschiedene reale Szenarien zu modellieren und zu analysieren, und sind daher eine grundlegende und zentrale Datenstruktur in der Informatik.

Eine Vielzahl von in der Softwarewelt verwendeten Problemlösungsalgorithmen basieren auf Diagrammen. Hier können Sie tiefer in die Grafik eintauchen Leitfaden zur Diagrammdatenstruktur.

Implementieren eines Diagramms in Golang

Um eine Datenstruktur selbst zu implementieren, müssen Sie in den meisten Fällen eine Implementierung durchführen Objektorientierte Programmierung (OOP) Konzepte, aber Implementierung von OOP in Go ist nicht genau das Gleiche wie in anderen Sprachen wie Java und C++.

Go verwendet Strukturen, Typen und Schnittstellen, um OOP-Konzepte zu implementieren, und das ist alles, was Sie brauchen, um eine Diagrammdatenstruktur und ihre Methoden zu implementieren.

Ein Graph besteht aus Knoten (oder Eckpunkten) und Kanten. Ein Knoten ist eine Entität oder ein Element im Diagramm. Ein Beispiel für einen Knoten ist ein Gerät in einem Netzwerk oder eine Person in einem sozialen Netzwerk. Während eine Kante eine Verbindung oder Beziehung zwischen zwei Knoten ist.

Um einen Graphen in Go zu implementieren, müssen Sie zunächst eine Knotenstruktur definieren, deren Eigenschaft ihre Nachbarn sind. Die Nachbarn eines Knotens sind die anderen Knoten, die direkt mit dem Knoten verbunden sind.

In gerichteten Graphen haben Kanten eine Richtung, sodass nur die Knoten, auf die ein bestimmter Knoten zeigt, als seine Nachbarn betrachtet werden. In ungerichteten Graphen hingegen sind alle Knoten, die eine Kante mit einem Knoten teilen, dessen Nachbarn.

Der folgende Code zeigt, wie das funktioniert Knoten Struktur sieht aus:

type Node struct {
 Neighbors []*Node
}

In diesem Artikel liegt der Schwerpunkt auf einem ungerichteten Graphen. Um jedoch eine bessere Klarheit zu schaffen, finden Sie hier Folgendes: Knoten Die Struktur für einen gerichteten Graphen könnte wie folgt aussehen:

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

Mit dieser Definition ist die OutNeighbors Slice speichert die Knoten, zu denen vom aktuellen Knoten ausgehende Kanten vorhanden sind, und die InNachbarn Slice speichert die Knoten, von denen es eingehende Kanten zum aktuellen Knoten gibt.

Sie implementieren das Diagramm mithilfe einer Zuordnung von Ganzzahlen zu Knoten. Diese Karte dient als Adjazenzliste (die übliche Art, Diagramme darzustellen). Der Schlüssel dient als eindeutige ID für einen Knoten, während der Wert der Knoten ist.

Der folgende Code zeigt die Graph Struktur:

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

Man kann sich den Ganzzahlschlüssel auch als den Wert des Knotens vorstellen, dem er zugeordnet ist. In realen Szenarien könnte Ihr Knoten jedoch eine andere Datenstruktur sein, die das Profil einer Person oder etwas Ähnliches darstellt. In solchen Fällen sollten Sie die Daten als eine der Eigenschaften der Node-Struktur haben.

Sie benötigen eine Funktion, die als Konstruktor zum Initialisieren eines neuen Diagramms fungiert. Dadurch wird Speicher für die Adjazenzliste reserviert und Sie können dem Diagramm Knoten hinzufügen. Der folgende Code ist die Definition eines Konstruktors für Graph Klasse:

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

Sie können nun Methoden definieren, um verschiedene Arten von Operationen am Diagramm auszuführen. Es gibt verschiedene Vorgänge, die Sie an einem Diagramm ausführen können, vom Hinzufügen von Knoten über die Erstellung von Kanten zwischen Knoten bis hin zur Suche nach Knoten und mehr.

In diesem Artikel erkunden Sie die Funktionen zum Hinzufügen und Entfernen von Knoten und Kanten zu Diagrammen. Die folgenden Codeabbildungen sind die Implementierungen der Funktionen zum Ausführen dieser Vorgänge.

Hinzufügen eines Knotens zum Diagramm

Um dem Diagramm einen neuen Knoten hinzuzufügen, benötigen Sie die Einfügefunktion, die wie folgt aussieht:

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

Der AddNode Die Funktion fügt dem Diagramm einen neuen Knoten hinzu, wobei die ID als Parameter übergeben wird. Die Funktion prüft, ob bereits ein Knoten mit derselben ID vorhanden ist, bevor sie ihn zum Diagramm hinzufügt.

Hinzufügen einer Kante zum Diagramm

Die nächste wichtige Methode der Diagrammdatenstruktur ist die Funktion zum Hinzufügen einer Kante (also zum Herstellen einer Verbindung zwischen zwei Knoten). Da es sich hier um einen ungerichteten Graphen handelt, müssen Sie sich beim Erstellen von Kanten keine Gedanken über die Richtung machen.

Hier ist die Funktion zum Hinzufügen einer Kante zwischen zwei Knoten im Diagramm:

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

Ziemlich einfach! Das Hinzufügen von Kanten in einem ungerichteten Graphen ist einfach der Vorgang, bei dem beide Knoten einander benachbart werden. Die Funktion ruft beide Knoten anhand der ihr übergebenen IDs ab und hängt sie aneinander an Nachbarn Scheibe.

Entfernen einer Kante aus dem Diagramm

Um einen Knoten aus einem Diagramm zu entfernen, müssen Sie ihn aus allen Listen seiner Nachbarn entfernen, um sicherzustellen, dass es keine Dateninkonsistenzen gibt.

Der Vorgang zum Entfernen eines Knotens von allen seinen Nachbarn ist derselbe wie der Vorgang zum Entfernen von Kanten (oder Brechen). Verbindungen) zwischen den Knoten, daher müssen Sie zuerst die Funktion zum Entfernen von Kanten definieren, bevor Sie die Funktion zum Entfernen von Kanten definieren Knoten entfernen.

Nachfolgend finden Sie die Implementierung des RemoveEdge Funktion:

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

Der RemoveEdge Die Funktion akzeptiert zwei Knoten als Parameter und sucht nach dem Index des zweiten (Nachbar-)Knotens in der Nachbarnliste des Hauptknotens. Anschließend wird der Nachbar entfernt Knoten. Nachbarn mit einer Technik namens die Scheibe schneiden.

Die Entfernung funktioniert, indem die Elemente des Slice bis zum angegebenen Index (aber nicht einschließlich) und Elemente des Slice ab dem angegebenen Index genommen und verkettet werden. Belassen des Elements am angegebenen Index.

In diesem Fall haben Sie einen ungerichteten Graphen, daher sind seine Kanten bidirektional. Aus diesem Grund mussten Sie anrufen RemoveEdge Hauptsächlich zweimal Kante entfernen Funktion zum Entfernen des Nachbarn aus der Liste des Knotens und umgekehrt.

Entfernen eines Knotens aus dem Diagramm

Sobald Sie Kanten entfernen können, können Sie auch Knoten entfernen. Nachfolgend finden Sie die Funktion zum Entfernen von Knoten aus dem Diagramm:

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

Die Funktion akzeptiert die ID des Knotens, den Sie entfernen müssen. Es prüft, ob der Knoten existiert, bevor alle seine Kanten entfernt werden. Anschließend wird der Knoten mithilfe der integrierten Funktion von Go aus dem Diagramm gelöscht löschen Funktion.

Sie können sich dafür entscheiden, weitere Methoden für Ihr Diagramm zu implementieren, z. B. Funktionen zum Durchlaufen des Diagramms mithilfe der Abteilungssuche oder der Breitensuche oder eine Funktion zum Drucken des Diagramms. Sie können der Struktur jederzeit entsprechend Ihren Anforderungen Methoden hinzufügen.

Sie sollten auch beachten, dass Diagramme sehr effizient sind, aber bei unsachgemäßer Verwendung Ihre Anwendungsstruktur ruinieren können. Als Entwickler müssen Sie wissen, wie Sie Datenstrukturen für verschiedene Anwendungsfälle auswählen.

Erstellen Sie optimierte Software mit den richtigen Datenstrukturen

Go bietet bereits eine großartige Plattform zur Entwicklung effizienter Softwareanwendungen, aber wenn man sie vernachlässigt, ist das gut Je nach Entwicklungspraktiken kann es zu unterschiedlichen Problemen für die Architektur und Leistung Ihrer Anwendung kommen.

Eine wichtige Best Practice besteht darin, die richtigen Datenstrukturen wie Arrays, verknüpfte Listen und Diagramme für unterschiedliche Anforderungen zu übernehmen. Auf diese Weise können Sie sicherstellen, dass Ihre Anwendung ordnungsgemäß funktioniert, und müssen sich weniger Sorgen über mögliche Leistungsengpässe oder Ausfälle machen.