Grafy jsou jednou z nejdůležitějších datových struktur, které musíte jako programátor znát. Naučte se, jak jej implementovat v Golangu.

Problémy související s grafy se často objevují v softwarovém průmyslu. Ať už při technických pohovorech nebo při vytváření aplikací, které využívají grafy.

Grafy jsou základní datové struktury používané v různých aplikacích, od sociálních sítí a dopravních systémů až po doporučovací nástroje a síťové analýzy.

Co je to graf a jak můžete implementovat grafy v Go?

Co je to graf?

Graf je nelineární datová struktura, která představuje kolekci uzlů (nebo vrcholů) a spojení mezi nimi (hrany). Grafy jsou široce používány v softwarových aplikacích, které se intenzivně zabývají připojeními, jako jsou počítačové sítě, sociální sítě a další.

Graf je jedním z datové struktury, které byste měli znát jako programátor. Grafy poskytují výkonný a flexibilní způsob, jak modelovat a analyzovat různé scénáře reálného světa, a to z nich dělá základní a základní datovou strukturu v informatice.

instagram viewer

Široká škála algoritmů pro řešení problémů používaných ve světě softwaru je založena na grafech. V tomto se můžete hlouběji ponořit do grafů průvodce strukturou dat grafu.

Implementace grafu v Golangu

Pokud chcete implementovat datovou strukturu sami, musíte ji většinou implementovat objektově orientované programování (OOP) koncepty, ale implementace OOP v Go není úplně stejný jako v jiných jazycích, jako je Java a C++.

Go používá struktury, typy a rozhraní k implementaci konceptů OOP a to je vše, co potřebujete k implementaci grafové datové struktury a jejích metod.

Graf se skládá z uzlů (nebo vrcholů) a hran. Uzel je entita nebo prvek v grafu. Příkladem uzlu je zařízení v síti nebo osoba na sociální síti. Zatímco hrana je spojení nebo vztah mezi dvěma uzly.

Chcete-li implementovat graf v Go, musíte nejprve definovat strukturu uzlu, jehož vlastnost budou jeho sousedy. Sousedy uzlu jsou ostatní uzly, které jsou přímo připojeny k uzlu.

V orientovaných grafech mají hrany směr, takže za jeho sousedy jsou považovány pouze uzly, na které daný uzel ukazuje. Zatímco v neorientovaných grafech jsou všechny uzly, které sdílejí hranu s uzlem, jeho sousedy.

Následující kód ukazuje, jak Uzel struktura vypadá:

type Node struct {
 Neighbors []*Node
}

V tomto článku se zaměříme na neorientovaný graf. Pro lepší přehlednost je však uvedeno, co a Uzel struktura pro orientovaný graf může vypadat takto:

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

S touto definicí, OutNeighbors řez uloží uzly, ke kterým jsou odchozí hrany z aktuálního uzlu, a InNeighbors slice uloží uzly, ze kterých jsou příchozí hrany do aktuálního uzlu.

Graf implementujete pomocí mapy celých čísel k uzlům. Tato mapa slouží jako seznam sousedství (běžný způsob znázornění grafů). Klíč slouží jako jedinečné ID pro uzel, zatímco hodnota bude uzel.

Následující kód ukazuje Graf struktura:

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

Celočíselný klíč si lze také představit jako hodnotu uzlu, na který je mapován. Ačkoli ve scénářích reálného světa může být vaším uzlem jiná datová struktura představující profil osoby nebo něco podobného. V takových případech byste měli mít data jako jednu z vlastností struktury Node.

Potřebujete funkci, která bude fungovat jako konstruktor pro inicializaci nového grafu. Tím se přidělí paměť pro seznam sousedství a umožní vám přidávat uzly do grafu. Níže uvedený kód je definicí konstruktoru pro Graf třída:

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

Nyní můžete definovat metody pro provádění různých druhů operací s grafem. Existují různé operace, které můžete s grafem provádět, od přidávání uzlů po vytváření hran mezi uzly, vyhledávání uzlů a další.

V tomto článku prozkoumáte funkce pro přidávání uzlů a hran do grafů a také pro jejich odstraňování. Následující ilustrace kódu představují implementace funkcí pro provádění těchto operací.

Přidání uzlu do grafu

Chcete-li do grafu přidat nový uzel, potřebujete funkci vložení, která vypadá takto:

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 AddNode funkce přidá do grafu nový uzel s ID předaným jako parametr. Funkce zkontroluje, zda již existuje uzel se stejným ID, než jej přidá do grafu.

Přidání okraje do grafu

Další důležitou metodou datové struktury grafu je funkce přidání hrany (tj. vytvoření spojení mezi dvěma uzly). Vzhledem k tomu, že graf je zde neorientovaný, není třeba se při vytváření hran starat o směr.

Zde je funkce pro přidání hrany mezi dva uzly v grafu:

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

Docela jednoduché! Přidání hran v neorientovaném grafu je jednoduše proces, při kterém se oba uzly navzájem sousedí. Funkce získá oba uzly pomocí ID, která jí byla předána, a oba je připojí k sobě navzájem Sousedé plátek.

Odstranění okraje z grafu

Chcete-li odebrat uzel z grafu, musíte jej odstranit ze všech seznamů jeho sousedů, abyste zajistili, že nedochází k nekonzistencím dat.

Proces odstranění uzlu ze všech jeho sousedů je stejný jako proces odstranění hran (nebo zlomení spojení) mezi uzly, proto musíte nejprve definovat funkci pro odstranění hran, než definujete jednu do odstranit uzly.

Níže je uvedena implementace removeEdge funkce:

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 removeEdge funkce přijímá dva uzly jako parametry a hledá index druhého (sousedního) uzlu v seznamu sousedů hlavního uzlu. Poté pokračuje v odstranění souseda uzel. Sousedé pomocí techniky tzv krájení plátku.

Odstranění funguje tak, že se prvky řezu převezmou až po (ale nezahrnuje) zadaný index a prvky řezu za zadaným indexem a zřetězí se. Ponechání prvku na zadaném indexu mimo.

V tomto případě máte neorientovaný graf, proto jsou jeho hrany obousměrné. Proto jste museli zavolat removeEdge dvakrát v hlavní RemoveEdge funkce k odstranění souseda ze seznamu uzlu a naopak.

Odstranění uzlu z grafu

Jakmile budete moci odstranit hrany, můžete také odstranit uzly. Níže je uvedena funkce pro odstranění uzlů 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")
}

Funkce přijímá ID uzlu, který potřebujete odstranit. Než dojde k odstranění všech jeho hran, zkontroluje, zda uzel existuje. Poté odstraní uzel z grafu pomocí vestavěného Go vymazat funkce.

Můžete si vybrat implementaci více metod pro váš graf, jako jsou funkce pro procházení grafu pomocí vyhledávání na prvním místě nebo vyhledávání na šířku, nebo funkce pro tisk grafu. Do struktury můžete vždy přidat metody podle svých potřeb.

Měli byste také poznamenat, že grafy jsou velmi efektivní, ale pokud se nepoužívají správně, mohou zničit strukturu vaší aplikace. Jako vývojář musíte vědět, jak vybrat datové struktury pro různé případy použití.

Vytvářejte optimalizovaný software pomocí správných datových struktur

Go již poskytuje skvělou platformu pro vývoj efektivních softwarových aplikací, ale když zanedbáte dobré vývojové postupy, může to způsobit různé problémy s architekturou a výkonem vaší aplikace.

Jedním z důležitých osvědčených postupů je přijetí správných datových struktur, jako jsou pole, propojené seznamy a grafy, pro různé potřeby. Díky tomu můžete zajistit, aby vaše aplikace fungovala správně, a méně se starat o problémová místa výkonu nebo selhání, která mohou nastat.