Implement BFS with directed graph

GO code

package main
import "fmt"

/*	
	Test graph :
	0 <---4---->1
	^ 	    ^
	|	    |
	|	    |
    	5---->2---->3 
*/

type Node struct{
    next *Node
    data int
}

type Queue struct {
    top *Node
    size int
}

func (q *Queue)enqueue(data int) {
    newNode := &Node{data : data}
    if q.top == nil {
        q.top = newNode
    } else {
        q.top.next = newNode
    }
    q.size++
}

func (q *Queue)dequeue() int {
    if q.top == nil {
        fmt.Errorf( "Queue has no item" )
        return -1
    }
    result := q.top.data
    q.top = q.top.next
    q.size--
    return result
}

type Vertex struct{
    key int
    adjacent []*Vertex
}

type Graph struct {
    vertices []*Vertex
}

func (g *Graph)AddVertex(vertex int) {
    if g.vertices == nil {
        g.vertices = []*Vertex{}
    } else if contains(g.vertices, vertex) {
        fmt.Errorf( "Vertex %d already exists", vertex )
        return
    }
    g.vertices = append(g.vertices, &Vertex{key:vertex})
}

func (g *Graph)AddEdge(start, end int) {
    if g.vertices == nil {
        fmt.Errorf( "Graph doesn't have any vertex" )
        return
    }
    startV := g.getVertex(start)
    if startV == nil {
        fmt.Errorf( "Vertex %d doesn't exists", start )
        return
    }
    endV := g.getVertex(end)
    if endV == nil {
        fmt.Errorf( "Vertex %d doesn't exists", end )
        return
    }
    if startV.adjacent == nil {
        startV.adjacent = []*Vertex{}
    }
    if contains(startV.adjacent, end) {
        fmt.Errorf( "Edge %d->%d already exists", start, end )
        return
    }
    startV.adjacent = append(startV.adjacent, endV)
}


func (g *Graph)IsLinked(start, end int) bool {
    if g.vertices == nil {
        fmt.Errorf( "Graph doesn't have any vertex" )
        return false
    }
    startV := g.getVertex(start)
    if startV == nil {
        fmt.Errorf( "Vertex %d doesn't exists", start )
        return false
    } else if len(startV.adjacent) == 0 {
        fmt.Errorf( "Vertex %d doesn't have any adjacent vertex", start )
        return false
    }
    endV := g.getVertex(end)
    if endV == nil {
        fmt.Errorf( "Vertex %d doesn't exists", end )
        return false
    }
    
    return g.BFS(start, end)
}

func (g *Graph)BFS(start, end int) bool {
    visited := map[int]bool{}
    q := &Queue{}
    q.enqueue(start)
    for q.size > 0 {
        key := q.dequeue()
        if key == end {
            return true
        }
        if _, ok := visited[key]; ok {
            // already visited
            continue
        }
        visited[key] = true
        
        v := g.getVertex(key)
        for _, adjacentV := range v.adjacent {
            q.enqueue(adjacentV.key)
        }
    }
    return false
}


func (g *Graph)getVertex(key int) *Vertex {
     for _, v := range g.vertices {
        if v.key == key {
            return v
        }
    }
    fmt.Errorf( "Can't get vertex %d", key )
    return nil
}

func contains(vertices []*Vertex, key int) bool {
    for _, v := range vertices {
        if v.key == key {
            return true
        }
    }
    return false
}

func main() {
    g := &Graph{}
    g.AddVertex(0)
    g.AddVertex(1)
    g.AddVertex(2)
    g.AddVertex(3)
    g.AddVertex(4)
    g.AddVertex(5)
    
    g.AddEdge(2, 3)
    g.AddEdge(3, 1)
    g.AddEdge(4, 0)
    g.AddEdge(4, 1)
    g.AddEdge(5, 0)
    g.AddEdge(5, 2)
    
    fmt.Printf( "Is %d -> %d linked ? : %t\n", 0, 3, g.IsLinked(0, 3) )
    fmt.Printf( "Is %d -> %d linked ? : %t\n", 3, 0, g.IsLinked(3, 0) )
    fmt.Printf( "Is %d -> %d linked ? : %t\n", 1, 4, g.IsLinked(1, 4) )
    fmt.Printf( "Is %d -> %d linked ? : %t\n", 5, 1, g.IsLinked(5, 1) )
    fmt.Printf( "Is %d -> %d linked ? : %t\n", 1, 5, g.IsLinked(1, 5) )
}

output

Is 0 -> 3 linked ? : false
Is 3 -> 0 linked ? : false
Is 1 -> 4 linked ? : false
Is 5 -> 1 linked ? : true
Is 1 -> 5 linked ? : false

execution time

O(V + E)

V : the number of vertices
E : the number of edges