Реализация ДПП


Я реализовал ДПП с использованием рекурсии в ходу. Когда я ДПП график, я могу получить путь обхода. Но я уверен, что еще я могу добавить к этому ДПП для того, чтобы сделать поиск лучше.

Кроме того, есть ли польза от использования стека вместо традиционных рекурсии? Я знаю, что рекурсия использует стек в качестве базовой структуры данных. Я также установив емкость списка для каждой вершины.

ДПП.перейти

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)
}


558
3
задан 26 января 2018 в 07:01 Источник Поделиться
Комментарии
1 ответ

Я думаю, что рекурсия здесь довольно элегантно (знать о производительности, вы должны сделать несколько тестов).

Что касается вашего кода, я хотел бы предложить некоторые незначительные изменения, чтобы сделать его более читабельным:


  1. if vertex.visited != true { такой же, как и if !vertex.visited {

  2. первая ручка конкретных случаях с раннего возврата, а затем общий случай: таким образом дополненной отступ касается только конкретных случаев

  3. вы можете перебрать пустой (или даже нулевой) срез

  4. используйте распаковки

  5. Я не думаю, что инициализация емкость нарезать много приносит

Код переписан с этого изменения:

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)
}

1
ответ дан 2 февраля 2018 в 09:02 Источник Поделиться