# Build Directed Graph

📚 4 min read Tweet this post
Section titled Introduction

## 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.

Section titled Use%20case

## 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:

1. 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.
2. 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.
3. 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.
4. 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.
5. 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.

Section titled Code%20Time

## 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.

go data-structure graph