Processamento de Dados Massivos/Projeto e implementação de aplicações Big Data/Identificação de ciclos em grafos: diferenças entre revisões

[edição não verificada][edição não verificada]
Conteúdo apagado Conteúdo adicionado
mSem resumo de edição
Sem resumo de edição
Linha 51:
 
No passo (d) do exemplo, todos os três vértices detectam o ciclo (2,3,4). Para assegurar que apenas um dos vértices reportem a detecção, pode-se detectar o ciclo apenas do vértice cujo identificador seja o menor (por algum critério de ordenação) dentre os demais vértices do ciclo, onde no exemplo seria o vértice 2.
 
==== Análise do Algoritmo ====
 
O número total de iterações do algoritmo paralelo será igual ao tamanho do maior caminho de vértices distintos do grafo mais algumas poucas iterações iniciais ou finais. Portanto o número de iterações do algoritmo paralelo será Θ(|V|), sendo que o maior caminho distinto possível de um grafo seria contendo todos os vértices do grafo.
 
==== Pseudo-Código no Modelo Pregel de Programação Paralela ====