Big Data Week Brasil

Um ótimo blog sobre Big Data Analytics com artigos, ebooks e vídeos abordando as aplicações de Big Data Analytics no Brasil e no mundo.
13
Aug

Uma visão geral do funcionamento de grafos em estruturas de dados

Uma rápida introdução aos grafos nas estruturas de dados e como os grafos podem ser usados ​​para descrever as relações reais entre diferentes tipos de dados.

Este artigo tem como objetivo fornecer uma introdução básica dos grafos nas estruturas de dados e os algoritmos que são comumente usados ​​para percorrer esses grafos. Grafos e algoritmos são os temas de algumas das perguntas mais frequentes no processo de entrevista.

Os grafos são uma das estruturas de dados mais interessantes em ciência da computação, eles são uma ferramenta poderosa e versátil que nos permite representar facilmente a relação entre vários tipos de dados. As duas partes principais de um grafo são vértices (nós) nos quais os dados são armazenados, ou seja, as letras na imagem acima e as arestas que conectam esses nós entre si.

Os grafos podem ser direcionados e não direcionados.

  • Grafo Não Dirigido: Um grafo não direcionado significa que, se tivermos uma aresta entre dois nós, A e B, então assumimos que existe um caminho de A para B, bem como de B para A.
  • Grafo Dirigido: Um grafo direcionado tem setas nas arestas que representam a direção do relacionamento, ou seja, se tivermos uma aresta entre dois nós, A e B, direcionados de A para B, então o caminho existe apenas de A para B e não de B para A.
  • Grafos Ponderados: Este tipo de grafo tem um peso ou número associado a cada borda.

 

Agora vamos falar sobre os algoritmos usados ​​para percorrer os grafos. Atravessar um grafo significa examinar todos os nós e vértices do grafo. Existem dois métodos gerais usados ​​para percorrer um grafo:

  • Busca em Profundidade: A pesquisa de profundidade (Depth First Search – DFS) começa com o nó inicial e, em seguida, vai cada vez mais fundo até encontrarmos o nó a ser localizado ou o nó que não possui filhos. Quando chegamos a um nó que não tem mais filhos, voltamos ao nó mais recente que ainda tem nós para explorar. Pilha é uma estrutura de dados que usa o algoritmo DFS.

Etapas para o DFS :

Etapa 1:  SET STATUS = 1 (estado pronto) para cada nó em G.

Passo 2: Coloque o nó inicial A na pilha e defina seu STATUS = 2 (estado de espera).

Etapa 3: Repita as etapas 4 e 5 até que a pilha esteja vazia.

Etapa 4:  Remova o nó superior da pilha. Processe esse nó e defina seu STATUS = 3 (estado processado).

Passo 5:  Coloque na pilha todos os vizinhos de N que estão no estado pronto (STATUS = 1) e defina seu STATUS = 2 (estado de espera)
[END OF LOOP]

Etapa 6:  SAÍDA

Por exemplo:

Atravessando este gráfico usando o DFS, obteremos:

A → B → E → C → F → D

Busca em largura:  O algoritmo de busca em largura (Breadth First Search – BFS) começa a atravessar o grafo a partir do nó raiz e passa a explorar todos os seus nós adjacentes. Depois que todos os seus nós adjacentes são explorados, ele seleciona um nó vizinho e explora todos os seus nós adjacentes. Esse processo é repetido até alcançarmos o nó a ser localizado.

Passos para o BFS:

Etapa 1:  SET STATUS = 1 (estado pronto) para cada nó em G

Etapa 2: Enfileire o nó inicial A e defina seu STATUS = 2 (estado de espera)

Etapa 3:  repita as etapas 4 e 5 até que a fila esteja vazia

Etapa 4: Desenfileire um nó N. Processe e defina seu STATUS = 3 (estado processado).

Etapa 5: Enfileire todos os vizinhos de N que estão no estado pronto (cujo STATUS = 1) e defina seu STATUS = 2 (estado de espera) [END OF LOOP]

Etapa 6:  SAÍDA

Por exemplo:

Atravessando este grafo usando o BFS, obteremos:

A → B → C → D → E → F

Espero que este artigo tenha ajudado a fornecer uma rápida introdução a estrutura de dados de grafos e como os grafos podem ser usados ​​para descrever as relações reais entre diferentes tipos de dados.

 

Tradução de: https://dzone.com/articles/an-overview-to-working-of-graphs-in-data-structure

Leave a Reply