Build Directed Graph
March 21, 2023
Introduction
Graphs are a fundamental data structure in computer science, used to represent relationships between objects in a wide range of applications. In this article, we will explore how to build a graph in Go, one of the most popular programming languages used for building networked and distributed systems.
Before we start, let's briefly define what a graph is. A graph is a collection of nodes or vertices, each of which may be connected to other nodes by edges. Edges can be directed or undirected, and can have weights or costs associated with them. Graphs are used to represent a variety of data structures, such as social networks, road networks, computer networks, and more.
Use case
Graphs are used in a wide range of applications in computer science and beyond. Here are a few examples of use cases where graphs are particularly useful:

Social networks: Social networks are naturally represented as graphs, where users are represented as nodes and their connections as edges. Graph algorithms can be used to analyze social networks, find clusters of users with similar interests, or identify influencers in the network.

Mapping and routing: Graphs are commonly used to represent maps, with nodes representing cities or landmarks, and edges representing roads or other routes between them. Graph algorithms can be used to find the shortest path between two points, or to identify regions that are not easily accessible.

Computer networks: Networks of computers can be represented as graphs, with nodes representing individual computers or network devices, and edges representing connections between them. Graph algorithms can be used to identify bottlenecks in the network, find the most efficient routing paths, or detect anomalies and security threats.

Recommendation systems: Recommendation systems often rely on graph algorithms to analyze large datasets of user preferences and suggest new items or content that users may be interested in. Graphs can be used to model the relationships between users and items, and algorithms can be used to identify patterns and similarities in the data.

Biological systems: Graphs are used to represent complex biological systems such as protein interactions, gene regulatory networks, and brain activity. Graph algorithms can be used to analyze these systems and identify patterns or anomalies that may be important for understanding biological processes or developing new therapies.
These are just a few examples of the many applications of graphs in computer science and other fields. By using graph algorithms and data structures, we can solve complex problems and gain new insights into the world around us.
Code Time
To build a graph in Go, we will create three types: Node
, Edge
, and Graph
.
type Node struct { Value string Edges []*Edge}type Edge struct { Start *Node End *Node Cost int}type Graph struct { Nodes []*Node}
The Node
type represents a node in the graph, and contains a Value
field that can be used to store any type of value associated with the node. The Edges
field is a slice of Edge
pointers that represents the edges of the node.
The Edge
type represents an edge in the graph, and contains two fields: Start
and End
, which are pointers to the start and end nodes of the edge, respectively. The Cost
field is an integer that represents the cost or weight of the edge.
The Graph
type represents the graph itself, and contains a slice of Node
pointers. This allows us to keep track of all the nodes in the graph.
Now that we have defined our types, let's create some methods to add nodes and edges to the graph.
func (g *Graph) AddNode(value string) *Node { node := &Node{ Value: value, } g.Nodes = append(g.Nodes, node) return node}func (g *Graph) AddEdge(start, end *Node, cost int) { edge := &Edge{ Start: start, End: end, Cost: cost, } start.Edges = append(start.Edges, edge)}
Now, let's define a method to get the neighbors of a node.
func (n *Node) Neighbors() []*Node { neighbors := []*Node{} for _, edge := range n.Edges { neighbors = append(neighbors, edge.End) } return neighbors}
The Neighbors method returns a slice of its neighboring nodes.
Finally, let's define a method to find a minimum cost from node start
to end
using Djikstra algorithms.
func (g *Graph) MinCost(start, end *Node) int { visited := make(map[*Node]bool) costs := make(map[*Node]int) // initialize all costs to infinity except for the starting node for _, node := range g.Nodes { costs[node] = math.MaxInt32 } costs[start] = 0 for { // find the unvisited node with the smallest cost var node *Node minCost := math.MaxInt32 for _, n := range g.Nodes { if !visited[n] && costs[n] < minCost { minCost = costs[n] node = n } } if node == nil { break // no path found } visited[node] = true for _, neighbor := range node.Neighbors() { if !visited[neighbor] { cost := costs[node] + g.getCost(node, neighbor) if cost < costs[neighbor] { costs[neighbor] = cost } } } } // return the cost of the path from start to end return costs[end]}
You can find the full code in https://go.dev/play/p/dcAHKXbOGac (opens in a new tab).