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
Sem resumo de edição |
Sem resumo de edição |
||
Linha 3:
=== Detecção de Ciclos por Busca em Profundidade ===
Um método
==== Pseudo-Código ====
'''Entrada''': Um grafo ''G'' e um vértice ''v'' de G
1 '''procedimento''' DFS(''G'',''v''):
2 marcar ''v'' como explorada
3 '''para cada''' aresta e em G.arestasAdjacentes(v) '''fazer'''
4 '''se''' aresta ''e'' estiver não-explorada '''então'''
5 ''w'' ← G.vérticeAdjacente(''v'',''e'')
6 '''se''' vértice ''w'' estiver não-explorado '''então'''
7 marcar ''e'' como uma aresta de avanço
8 chamar recursivamente DFS(G,''w'')
9 '''senão'''
10 marcar ''e'' como aresta de retorno
11 todo o caminho de ''w'' até ''v'' representa um ciclo
[[Ficheiro:GraphDFS.png|commoldura|centro|Detecção de Ciclos por Busca em Profundidade]]
Linha 9 ⟶ 24:
=== Detecção de Ciclos no Contexto de Dados Massivos ===
No contexto de dados massivos
Portanto, é necessário um algoritmo que divida o problema de detecção de ciclos em subproblemas entre nós de computação, de modo que os nós busquem por cíclos de maneira paralela, garantindo que todos os ciclos serão encontrados. Propõe-se então, um algoritmo para detecção de ciclos de grafo por passagem de mensagens entre os vértices, baseado no modelo Pregel de processamento de grafos da Google. Esse modelo apresenta uma abordagem centrada nos vértices em que os vértices do grafo trabalham juntos para detectar ciclos.
| |||