I am trying to implement a Graph
data structure in Golang and choose to use adjacency list representation. When starting to implement adjacency list, I have an idea that if I use map instead of list. I think (not sure though) this is much much easier to implement and I can find element in \$O(1)\$ rather using \$O(n)\$. I hope anyone can help review my code and the correct way to do adjacency graph.
I try to make it general by declaring payload as a new Interface
type which needs a Compare()
method to use in BFS and DFS later on.
type Graph struct {
nodes map[int]Node
}
type Node struct {
payload Interface
adjNodes map[int]struct{}
}
func (g *Graph) addNode(key int, payload Interface) {
if _, ok := g.nodes[key]; ok {
return
}
g.nodes[key] = Node{payload: payload, adjNodes: make(map[int]struct{})}
}
func (g *Graph) addEdge(src, dst int) {
// expand if no this node in graph
if src < 0 || dst < 0 {
panic("Node number can't be below 0")
}
// check if node exists
if _, ok := g.nodes[src]; !ok {
panic("No node " + string(src))
}
if _, ok := g.nodes[dst]; !ok {
panic("No node " + string(dst))
}
// connect by adjacent list
g.nodes[src].adjNodes[dst] = struct{}{}
g.nodes[dst].adjNodes[src] = struct{}{}
}