Jak zaimplementować strukturę danych wykresu w Golang

Problemy związane z wykresami często pojawiają się w branży oprogramowania. Czy to w wywiadach technicznych, czy podczas tworzenia aplikacji wykorzystujących grafy.

Wykresy to podstawowe struktury danych używane w różnych aplikacjach, od sieci społecznościowych i systemów transportowych po silniki rekomendacji i analizę sieci.

Co to jest wykres i jak można go zaimplementować w Go?

Co to jest wykres?

Graf to nieliniowa struktura danych reprezentująca zbiór węzłów (lub wierzchołków) i połączeń między nimi (krawędzi). Wykresy są szeroko stosowane w aplikacjach, które mają duży wpływ na połączenia, takie jak sieci komputerowe, sieci społecznościowe i inne.

Wykres jest jednym z struktury danych, które powinieneś znać jako programista. Wykresy zapewniają potężny i elastyczny sposób modelowania i analizowania różnych rzeczywistych scenariuszy, co czyni je podstawową i podstawową strukturą danych w informatyce.

Szeroka gama algorytmów rozwiązywania problemów stosowanych w świecie oprogramowania opiera się na grafach. Możesz zagłębić się w wykresy w tym przewodnik po strukturze danych grafu.

Implementacja wykresu w Golang

W większości przypadków, aby samodzielnie zaimplementować strukturę danych, musisz ją zaimplementować programowanie obiektowe (OOP) koncepcje, ale wdrażanie OOP w Go nie jest dokładnie taki sam, jak w innych językach, takich jak Java i C++.

Go używa struktur, typów i interfejsów do implementacji koncepcji OOP, a to wszystko, czego potrzebujesz, aby zaimplementować grafową strukturę danych i jej metody.

Graf składa się z węzłów (lub wierzchołków) i krawędzi. Węzeł to jednostka lub element na grafie. Przykładem węzła jest urządzenie w sieci lub osoba w sieci społecznościowej. Podczas gdy krawędź jest połączeniem lub relacją między dwoma węzłami.

Aby zaimplementować graf w Go, musisz najpierw zdefiniować strukturę węzłów, której właściwością będą jej sąsiedzi. Sąsiadami węzła są inne węzły, które są bezpośrednio połączone z węzłem.

W grafach skierowanych krawędzie mają kierunki, więc tylko węzły, na które wskazuje dany węzeł, są uważane za jego sąsiadów. W grafach nieskierowanych wszystkie węzły, które mają wspólną krawędź z węzłem, są jego sąsiadami.

Poniższy kod demonstruje, w jaki sposób Węzeł wygląd struktury:

type Node struct {
 Neighbors []*Node
}

W tym artykule skupimy się na grafie nieskierowanym. Jednak, aby zapewnić lepszą przejrzystość, oto co a Węzeł struktura dla grafu skierowanego może wyglądać następująco:

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

Z tą definicją, Sąsiedzi slice będzie przechowywać węzły, do których istnieją krawędzie wychodzące z bieżącego węzła, a plik u sąsiadów slice będzie przechowywać węzły, z których przychodzą krawędzie do bieżącego węzła.

Zaimplementujesz graf, używając mapy liczb całkowitych do węzłów. Ta mapa służy jako lista sąsiedztwa (powszechny sposób przedstawiania wykresów). Klucz służy jako unikalny identyfikator węzła, a wartością będzie węzeł.

Poniższy kod przedstawia Wykres struktura:

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

Klucz całkowity można również wyobrazić sobie jako wartość węzła, do którego jest odwzorowany. Chociaż w rzeczywistych scenariuszach twój węzeł może być inną strukturą danych reprezentującą profil osoby lub coś podobnego. W takich przypadkach powinieneś mieć dane jako jedną z właściwości struktury Node.

Potrzebujesz funkcji, która będzie działać jako konstruktor do inicjowania nowego wykresu. Spowoduje to przydzielenie pamięci dla listy sąsiedztwa i umożliwi dodanie węzłów do grafu. Poniższy kod jest definicją konstruktora dla Wykres klasa:

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

Możesz teraz zdefiniować metody wykonywania różnego rodzaju operacji na grafie. Istnieją różne operacje, które można wykonać na wykresie, od dodawania węzłów po tworzenie krawędzi między węzłami, wyszukiwanie węzłów i nie tylko.

W tym artykule poznasz funkcje dodawania węzłów i krawędzi do wykresów, a także ich usuwania. Poniższe ilustracje kodu to implementacje funkcji do wykonywania tych operacji.

Dodawanie węzła do wykresu

Aby dodać nowy węzeł do wykresu, potrzebujesz funkcji wstawiania, która wygląda tak:

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

The Dodajwęzeł Funkcja dodaje nowy węzeł na wykresie z identyfikatorem przekazanym mu jako parametr. Funkcja sprawdza, czy węzeł o tym samym identyfikatorze już istnieje przed dodaniem go do grafu.

Dodawanie krawędzi do wykresu

Następną ważną metodą struktury danych grafu jest funkcja dodawania krawędzi (czyli tworzenia połączenia między dwoma węzłami). Ponieważ wykres tutaj jest nieskierowany, nie ma potrzeby martwić się o kierunek podczas tworzenia krawędzi.

Oto funkcja dodająca krawędź między dwoma węzłami na wykresie:

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

Dość proste! Dodawanie krawędzi w grafie nieskierowanym jest po prostu procesem polegającym na tym, że oba węzły są ze sobą sąsiadami. Funkcja pobiera oba węzły na podstawie przekazanych jej identyfikatorów i dołącza je do siebie Sąsiedzi plasterek.

Usuwanie krawędzi z wykresu

Aby usunąć węzeł z grafu, musisz usunąć go ze wszystkich list sąsiadów, aby upewnić się, że nie ma niespójności danych.

Proces usuwania węzła od wszystkich jego sąsiadów jest taki sam, jak proces usuwania krawędzi (lub łamania połączenia) między węzłami, dlatego musisz najpierw zdefiniować funkcję usuwania krawędzi przed zdefiniowaniem tej, do której usunąć węzły.

Poniżej realizacja ww usuń krawędź funkcjonować:

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

The usuń krawędź funkcja przyjmuje dwa węzły jako parametry i szuka indeksu drugiego (sąsiedniego) węzła na liście sąsiadów węzła głównego. Następnie idzie do przodu, aby usunąć sąsiada węzeł. Sąsiedzi stosując technikę tzw krojenie plasterka.

Usunięcie polega na przeniesieniu elementów wycinka do (ale nie włączając) określonego indeksu oraz elementów wycinka od określonego indeksu i połączeniu ich. Pozostawienie elementu o określonym indeksie poza.

W tym przypadku masz graf nieskierowany, dlatego jego krawędzie są dwukierunkowe. Dlatego trzeba było zadzwonić do usuń krawędź dwa razy w głównym Usuń krawędź funkcja usuwania sąsiada z listy węzłów i odwrotnie.

Usuwanie węzła z wykresu

Gdy będziesz w stanie usunąć krawędzie, możesz także usunąć węzły. Poniżej znajduje się funkcja usuwania węzłów z grafu:

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

Funkcja akceptuje identyfikator węzła, który należy usunąć. Sprawdza, czy węzeł istnieje przed przystąpieniem do usuwania wszystkich jego krawędzi. Następnie usuwa węzeł z wykresu za pomocą wbudowanego Go usuwać funkcjonować.

Możesz zdecydować się na zaimplementowanie większej liczby metod dla swojego wykresu, takich jak funkcje do przechodzenia przez wykres przy użyciu przeszukiwania w pierwszej kolejności lub przeszukiwania wszerz lub funkcji drukowania wykresu. Zawsze możesz dodać metody do struktury zgodnie ze swoimi potrzebami.

Należy również zauważyć, że wykresy są bardzo wydajne, ale jeśli nie są używane prawidłowo, mogą zrujnować strukturę aplikacji. Jako programista musisz wiedzieć, jak wybrać struktury danych dla różnych przypadków użycia.

Twórz zoptymalizowane oprogramowanie przy użyciu właściwych struktur danych

Go już zapewnia doskonałą platformę do tworzenia wydajnych aplikacji, ale kiedy zaniedbujesz dobre praktyk programistycznych, może powodować różne problemy z architekturą i wydajnością aplikacji.

Jedną z ważnych najlepszych praktyk jest przyjęcie odpowiednich struktur danych, takich jak tablice, połączone listy i wykresy, do różnych potrzeb. Dzięki temu możesz mieć pewność, że Twoja aplikacja działa poprawnie i mniej martwić się o wąskie gardła wydajności lub awarie, które mogą się pojawić.