grafo-busca-profundidade

package main

import "fmt"

type Grafo struct {
	vertices []Vertice
}

type Vertice struct {
	color        string
	distancia    int
	predecessor  *Vertice
	valor        int
	tempoInicial int
	tempoFinal   int
}

func construirGrafo() Grafo {
	grafo := Grafo{
		vertices: []Vertice{},
	}
	vertice1 := Vertice{
		color:        "branco",
		distancia:    0,
		predecessor:  nil,
		valor:        1,
		tempoInicial: 0,
		tempoFinal:   0,
	}
	grafo.vertices = append(grafo.vertices, vertice1)

	vertice2 := Vertice{
		color:        "branco",
		distancia:    0,
		predecessor:  &vertice1,
		valor:        2,
		tempoInicial: 0,
		tempoFinal:   0,
	}
	grafo.vertices = append(grafo.vertices, vertice2)

	vertice3 := Vertice{
		color:        "branco",
		distancia:    0,
		predecessor:  &vertice2,
		valor:        3,
		tempoInicial: 0,
		tempoFinal:   0,
	}
	grafo.vertices = append(grafo.vertices, vertice3)

	vertice4 := Vertice{
		color:        "branco",
		distancia:    0,
		predecessor:  &vertice2,
		valor:        4,
		tempoInicial: 0,
		tempoFinal:   0,
	}
	grafo.vertices = append(grafo.vertices, vertice4)

	vertice5 := Vertice{
		color:        "branco",
		distancia:    0,
		predecessor:  &vertice1,
		valor:        5,
		tempoInicial: 0,
		tempoFinal:   0,
	}
	grafo.vertices = append(grafo.vertices, vertice5)

	return grafo
}

func buscaPorProfundidade(G Grafo) {
	for i := 0; i < len(G.vertices); i++ {
		if G.vertices[i].color == "branco" {
			visitarVertice(&G, &G.vertices[i])
		}
	}
}

func visitarVertice(G *Grafo, vertice *Vertice) {
	tempo := 1
	vertice.tempoInicial = tempo
	vertice.color = "cinza"
	adjacentes := buscarAdjacentes(G, vertice)
	for i := 0; i < len(adjacentes); i++ {
		if adjacentes[i].color == "branco" {
			visitarVertice(G, adjacentes[i])
		}
	}
	vertice.color = "preto"
	tempo += 1
	vertice.tempoFinal = tempo
	if vertice.predecessor == nil {
		fmt.Printf("Vertice %d não possui pai.\n", vertice.valor)
	} else {
		fmt.Printf("Vertice %d possui o pai: %#v\n", vertice.valor, vertice.predecessor.valor)
	}

	for i := 0; i < len(adjacentes); i++ {
		fmt.Printf("Vértice %d, possui os adjacentes: %d. \n", vertice.valor, adjacentes[i].valor)
	}
	fmt.Printf("Vértice %d | tempo inicial: %d | tempo final %d \n", vertice.valor, vertice.tempoInicial, vertice.tempoFinal)
}

func buscarAdjacentes(G *Grafo, verticeAtual *Vertice) []*Vertice {
	var adjacentes []*Vertice
	for i := 0; i < len(G.vertices); i++ {
		if G.vertices[i].predecessor == nil {
			continue
		}

		if G.vertices[i].predecessor.valor == verticeAtual.valor {
			adjacentes = append(adjacentes, &G.vertices[i])
		}
	}
	return adjacentes
}

func main() {
	grafo := construirGrafo()
	buscaPorProfundidade(grafo)
}