3
\$\begingroup\$

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)
}
\$\endgroup\$
1
\$\begingroup\$

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)
}
\$\endgroup\$
  • \$\begingroup\$ Better to change the line: fmt.Println(vertex) To: fmt.Println(vertex.value) \$\endgroup\$ – flashsnake Jan 20 at 23:44
  • \$\begingroup\$ 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) \$\endgroup\$ – oliverpool Jan 23 at 8:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.