## Brief of Graph

Graph is a non-linear data structure in programming. This data structure commonly implemented for short-path-finding and often use to validate programming skill in a Software Engineer job.

Graph built with connection nodes or commonly called **Vertex**, each connected Vertex called **Edge**, and distance of edge usually called **Adjacent**.

## The Algorithm

First of all, you need to define the data storage, let's use Golang `struct`

.

```
type Graph struct {
Vertice []*Vertex
}
type Vertex struct {
Key int
Adjacent []*Vertex
}
func isExist(key int, vertices []*Vertex) bool {
for _, v := range vertices {
if v.Key == key {
return true
}
}
return false
}
```

There are two data types defined that called *Graph* and *Vertex*. The Graph is base data type that store all Vertices that inputted in the main code in the future. Then Vertex defined to store the *Key* and all *Adjacent*.

In the section below the definition of types, the *isExist* function written to validate is inputted *Key* exist in vertices or not. We need to check the key to avoid duplicated inserted key into vertices.

Now, let's write a method of type of *Graph* to add the Vertices. This method consist of:

- Check is the
*Key*exists? - Add
*Key*into graph vertices.

```
func (g *Graph) AddVertex(vertex int) error {
// Check is vertex available
if isExist(vertex, g.Vertice) {
return fmt.Errorf("vertex is exist")
}
// Insert vertex into graph
g.Vertice = append(g.Vertice, &Vertex{
Key: vertex,
})
return nil
}
```

At this moment, we can add the vertex into our struct, but we need to get it. Let's write the *GetVertex* method in our code. We just need to get our vertex by it's key that inserted before. If the key is match, return the vertex from vertices.

```
func (g *Graph) GetVertex(vertex int) *Vertex {
for i, v := range g.Vertice {
if v.Key == vertex {
return g.Vertice[i]
}
}
return nil
}
```

Remember, we need to connect the vertex and to set the Edge and append the destination vertex into adjacent of current vertex. So, the logic suppose like this:

- Get the current Vertex (from Vertex) and destination vertex. If it's not exist, return error.
- Check the destination vertex in current adjacent is exist or not. It should be doesn't exist.
- If everything okay, let's insert destination vertex into current adjacent.

```
func (g *Graph) AddEdge(from int, dest int) error {
// Check is vertext exists
fromVertex := g.GetVertex(from)
destVertex := g.GetVertex(dest)
if fromVertex == nil || destVertex == nil {
return fmt.Errorf("vertex from (%v) --> (%v) is not valid", from, dest)
}
// Check is adjacent vertex exists or not
if isExist(destVertex.Key, fromVertex.Adjacent) {
return fmt.Errorf("edge from vertex (%v) --> (%v) already exists", fromVertex.Key, destVertex.Key)
}
// insert new adjacent for from and dest vertex
fromVertex.Adjacent = append(fromVertex.Adjacent, destVertex)
return nil
}
```

Finally, everything is set, and we need to print all vertex and its adjacent, let's write the code.

```
func (g *Graph) Print() {
for _, val := range g.Vertice {
fmt.Printf("(%v): ", val.Key)
for i, adj := range val.Adjacent {
if i > 0 {
fmt.Printf(" -> ")
}
fmt.Printf("(%v)", adj.Key)
}
fmt.Println()
}
}
```

## Let's run the code

To run these code, we need to write the main function.

```
func main() {
graph := &Graph{}
graph.AddVertex(0)
graph.AddVertex(1)
graph.AddVertex(2)
graph.AddVertex(3)
graph.AddVertex(4)
graph.AddVertex(5)
graph.AddVertex(6)
// Set the edges
graph.AddEdge(0, 1)
graph.AddEdge(0, 2)
graph.AddEdge(0, 5)
graph.AddEdge(1, 0)
graph.AddEdge(2, 0)
graph.AddEdge(5, 0)
graph.AddEdge(2, 1)
graph.AddEdge(2, 3)
graph.AddEdge(2, 6)
graph.AddEdge(1, 2)
graph.AddEdge(3, 2)
graph.AddEdge(6, 2)
graph.AddEdge(6, 5)
graph.AddEdge(5, 6)
graph.Print()
}
```

Output:

```
(0): (1) -> (2) -> (5)
(1): (0) -> (2)
(2): (0) -> (1) -> (3) -> (6)
(3): (2)
(4):
(5): (0) -> (6)
(6): (2) -> (5)
```

For the full code, please look at my gists here: Graph Gists

## Top comments (0)