DFS implementation

Question

I implemented DFS using recursion in Go. When I dfs the graph, I am able to get the path of traversal. But I'm unsure what else could I add to this DFS in order to make the search better.

Also, Is there any benefit from using a stack instead of traditional recursion? I know that recursion uses stack as underlying data structure. I'm also setting the capacity of list for every vertex.

dfs.go

package main
import (
 "fmt"
)
type Vertex struct {
 visited bool
 value string
 neighbours []*Vertex
}
func (v *Vertex) connect(vertex *Vertex) {
 v.neighbours = append(v.neighbours, vertex)
}
type Graph struct{}
func (g *Graph) dfs(vertex *Vertex) {
 if vertex.visited != true {
 vertex.visited = true
 fmt.Println(vertex)
 if len(vertex.neighbours) != 0 {
 for _, v := range vertex.neighbours {
 g.dfs(v)
 }
 } else {
 return
 }
 }
}
func (g *Graph) disconnected(vertices ...*Vertex){
 for _, v := range vertices{
 g.dfs(v)
 }
}
func main() {
 v1 := Vertex{false, "A", make([]*Vertex, 0, 5)}
 v2 := Vertex{false, "B", make([]*Vertex, 0, 5)}
 v3 := Vertex{false, "C", make([]*Vertex, 0, 5)}
 v4 := Vertex{false, "D", make([]*Vertex, 0, 5)}
 v5 := Vertex{false, "E", make([]*Vertex, 0, 5)}
 g := Graph{}
 v1.connect(&v2)
 v2.connect(&v4)
 v2.connect(&v5)
 v3.connect(&v4)
 v3.connect(&v5)
 g.dfs(&v1)
}

Answer 1

I think that a recursion is quite elegant here (to know about the performance, you would need to do some benchmarks).

Regarding your code, I would suggest some minor changes to make it more readable:

1. if vertex.visited != true { is the same as if !vertex.visited {
2. first handle specific cases with an early return and then the general case: this way augmented indentation concerns only the specific cases
3. you can iterate over an empty (or even nil) slice
4. use unpacking
5. I don't think that initializing the slice capacity brings much

Code rewritten with this changes:

package main
import (
 "fmt"
)
type Vertex struct {
 visited bool
 value string
 neighbours []*Vertex
}
func NewVertex(value string) *Vertex {
 return &Vertex{
 value: value,
 // the two following lines can be deleted, because the will be initialized with their null value
 visited: false,
 neighbours: nil, // comment 5.
 }
}
func (v *Vertex) connect(vertex ...*Vertex) { // see comment 4.
 v.neighbours = append(v.neighbours, vertex...)
}
type Graph struct{}
func (g *Graph) dfs(vertex *Vertex) {
 if vertex.visited { // see comment 1.
 return // see comment 2.
 }
 vertex.visited = true
 fmt.Println(vertex)
 for _, v := range vertex.neighbours { // see comment 3.
 g.dfs(v)
 }
}
func (g *Graph) disconnected(vertices ...*Vertex) {
 for _, v := range vertices {
 g.dfs(v)
 }
}
func main() {
 v1 := NewVertex("A")
 v2 := NewVertex("B")
 v3 := NewVertex("C")
 v4 := NewVertex("D")
 v5 := NewVertex("E")
 g := Graph{}
 v1.connect(v2)
 v2.connect(v4, v5) // see comment 4.
 v3.connect(v4, v5) // see comment 4.
 g.dfs(v1)
}

• flashsnake: Better to change the line: fmt.Println(vertex) To: fmt.Println(vertex.value)
• oliverpool: This is copy and paste of the original code: I don't think that it matters much (it really depends on what you want to see as output)