Percurso em profundidade

Beschreibung

1 Estrutura de dados (Notas) Notiz am Percurso em profundidade, erstellt von Rodrigo Amaral am 17/11/2015.
Rodrigo Amaral
Notiz von Rodrigo Amaral, aktualisiert more than 1 year ago
Rodrigo Amaral
Erstellt von Rodrigo Amaral vor etwa 9 Jahre
15
0

Zusammenfassung der Ressource

Seite 1

Percurso em profundidade Definição: (Depth-first search) Traça um caminho a partir de um nó inicial procurando o caminho mais longo possível a partir do mesmo(Figura 1). Esse caminho é gerado com a construção de um vetor de predecessores. Algoritmo: Utilizamos um algoritimo similar ao utilizado no percurso em largura. Basta trocarmos a estrutura de dados para uma PILHA e tratarmos o estado na mesma dentro do algoritmo.2 C(u) ← +∞, cor(u) ← branco, e P(u) ← nil. 3 Se u = u1 então 4 C(u) ← 0, empilha u em Q, e cor(u) ← cinza. 5 Enquanto Q 6= ∅ faça6 Desempilha u de Q e cor(u) ← preto. 7 Para todo v ∈ A(u), tal que cor(v) != preto faça: 8 P(v) ← u e C(v) ← C(u) + 1. 9 Se cor(u) = branco, então empilha v em Q e cor(v) ← cinza.

Zusammenfassung anzeigen Zusammenfassung ausblenden

ähnlicher Inhalt

Teoria dos Grafos
Natalie Bravo
Dijkstra
Rodrigo Amaral
Ferramentas de estudo Online GoConqr
GoConqr suporte .
Sócrates, Platão e Aristóteles
André Matias
Constituição Federal - Mnemônicos
tiago meira de almeida
Estruturas de dados de grafos
Marcell Alves
5 exercícios de cinemática
Felipe Maders
Símbolos e Abreviações para tomar Notas
miminoma
Símbolos e Abreviações para tomar Notas
GoConqr suporte .
BATERIA OFENSIVA - ESTRUTURA DE DADOS
DANIEL BARROSO
Teoria dos Grafos
Mateus Ferro