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)