java graph tutorial how implement graph data structure
Este tutorial abrangente do Java Graph explica em detalhes a estrutura de dados do gráfico. Inclui como criar, implementar, representar e atravessar gráficos em Java:
Uma estrutura de dados de gráfico representa principalmente uma rede conectando vários pontos. Esses pontos são chamados de vértices e os links que conectam esses vértices são chamados de ‘Bordas’. Portanto, um grafo g é definido como um conjunto de vértices V e arestas E que conectam esses vértices.
Os gráficos são usados principalmente para representar várias redes, como redes de computadores, redes sociais, etc. Eles também podem ser usados para representar várias dependências em software ou arquiteturas. Esses gráficos de dependência são muito úteis para analisar o software e também, às vezes, para depurá-lo.
=> Verifique TODOS os tutoriais Java aqui.
O que você aprenderá:
- Estrutura de dados do gráfico Java
- Como criar um gráfico?
- Implementação de Graph em Java
- Biblioteca Java Graph
- Conclusão
Estrutura de dados do gráfico Java
Dado a seguir é um gráfico com cinco vértices {A, B, C, D, E} e arestas dadas por {{AB}, {AC}, {AD}, {BD}, {CE}, {ED}}. Como as arestas não mostram nenhuma direção, este gráfico é conhecido como 'gráfico não direcionado'.
Além do gráfico não direcionado mostrado acima, existem várias variantes do gráfico em Java.
Vamos discutir essas variantes em detalhes.
Diferentes variantes de gráfico
A seguir estão algumas das variantes do gráfico.
# 1) Gráfico direcionado
Um gráfico ou dígrafo direcionado é uma estrutura de dados de gráfico em que as arestas têm uma direção específica. Eles se originam de um vértice e culminam em outro vértice.
O diagrama a seguir mostra o exemplo de gráfico direcionado.
No diagrama acima, há uma aresta do vértice A ao vértice B. Mas observe que A a B não é o mesmo que B a A como no gráfico não direcionado, a menos que haja uma aresta especificada de B a A.
Um grafo direcionado é cíclico se houver pelo menos um caminho que tenha seu primeiro e último vértice iguais. No diagrama acima, um caminho A-> B-> C-> D-> E-> A forma um ciclo direcionado ou gráfico cíclico.
Por outro lado, um gráfico acíclico direcionado é um gráfico no qual não há ciclo direcionado, ou seja, não há caminho que forme um ciclo.
# 2) Gráfico Ponderado
Em um gráfico ponderado, um pesoestá associado a cada borda do gráfico. O peso normalmente indica a distância entre os dois vértices. O diagrama a seguir mostra o gráfico ponderado. Como nenhuma direção é mostrada, este é o gráfico não direcionado.
Observe que um gráfico ponderado pode ser direcionado ou não direcionado.
Como criar um gráfico?
Java não fornece uma implementação completa da estrutura de dados do gráfico. No entanto, podemos representar o gráfico de forma programática usando Coleções em Java. Também podemos implementar um gráfico usando matrizes dinâmicas como vetores.
Normalmente, implementamos gráficos em Java usando a coleção HashMap. Os elementos HashMap estão na forma de pares de valores-chave. Podemos representar a lista de adjacências de grafos em um HashMap.
A maneira mais comum de criar um grafo é usando uma das representações de grafos como matriz de adjacência ou lista de adjacência. Discutiremos essas representações a seguir e, em seguida, implementaremos o grafo em Java usando a lista de adjacência para a qual usaremos ArrayList.
Representação gráfica em Java
A representação gráfica significa a abordagem ou técnica usando a qual os dados do gráfico são armazenados na memória do computador.
Temos duas representações principais de gráficos, conforme mostrado abaixo.
Matriz de adjacência
Matriz de Adjacência é uma representação linear de gráficos. Esta matriz armazena o mapeamento de vértices e arestas do gráfico. Na matriz de adjacência, os vértices do gráfico representam linhas e colunas. Isso significa que se o grafo tiver N vértices, a matriz de adjacência terá tamanho NxN.
Se V é um conjunto de vértices do gráfico, então a interseção Meu jna lista de adjacências = 1 significa que existe uma aresta entre os vértices i e j.
Para entender melhor este conceito de forma clara, vamos preparar uma Matriz de adjacência para um grafo não direcionado.
Como visto no diagrama acima, vemos que para o vértice A, as interseções AB e AE são definidas como 1, pois há uma aresta de A para B e A para E. Da mesma forma, a interseção BA é definida como 1, pois esta é uma gráfico e AB = BA. Da mesma forma, definimos todas as outras interseções para as quais há uma aresta como 1.
Caso o gráfico seja direcionado, a intersecção Meu jserá definido como 1 apenas se houver uma borda nítida direcionada de Vi a Vj.
Isso é mostrado na ilustração a seguir.
Como podemos ver no diagrama acima, há uma aresta de A a B. Portanto, a interseção AB é definida como 1, mas a interseção BA é definida como 0. Isso ocorre porque não há nenhuma aresta direcionada de B para A.
lista de endereços de e-mail falsos para usar
Considere os vértices E e D. Vemos que há arestas de E a D, bem como de D a E. Portanto, definimos essas duas interseções como 1 na matriz de adjacência.
Agora passamos para os gráficos ponderados. Como sabemos para o gráfico ponderado, um número inteiro também conhecido como peso está associado a cada aresta. Representamos esse peso na matriz de adjacência para a aresta que existe. Este peso é especificado sempre que houver uma aresta de um vértice para outro em vez de '1'.
Esta representação é mostrada abaixo.
Lista de Adjacência
Em vez de representar um grafo como uma matriz de adjacência que é sequencial por natureza, também podemos usar a representação vinculada. Essa representação vinculada é conhecida como lista de adjacências. Uma lista de adjacências nada mais é do que uma lista encadeada e cada nó da lista representa um vértice.
A presença de uma aresta entre dois vértices é denotada por um ponteiro do primeiro vértice para o segundo. Essa lista de adjacências é mantida para cada vértice do grafo.
Quando percorremos todos os nós adjacentes de um determinado nó, armazenamos NULL no próximo campo de ponteiro do último nó da lista de adjacências.
Agora usaremos os gráficos acima que usamos para representar a matriz de adjacência para demonstrar a lista de adjacências.
A figura acima mostra a lista de adjacências para o grafo não direcionado. Vemos que cada vértice ou nó possui sua lista de adjacências.
No caso do grafo não direcionado, os comprimentos totais das listas de adjacência são geralmente o dobro do número de arestas. No gráfico acima, o número total de arestas é 6 e o total ou soma do comprimento de toda a lista de adjacências é 12.
Agora vamos preparar uma lista de adjacências para o grafo direcionado.
Como visto na figura acima, no grafo direcionado o comprimento total das listas de adjacências do grafo é igual ao número de arestas no grafo. No gráfico acima, existem 9 arestas e a soma dos comprimentos das listas de adjacência para este gráfico = 9.
Agora vamos considerar o seguinte gráfico direcionado ponderado. Observe que cada aresta do gráfico ponderado tem um peso associado a ela. Portanto, quando representamos este gráfico com a lista de adjacências, temos que adicionar um novo campo a cada nó da lista que denotará o peso da aresta.
A lista de adjacências para o gráfico ponderado é mostrada abaixo.
O diagrama acima mostra o grafo ponderado e sua lista de adjacências. Observe que há um novo espaço na lista de adjacências que denota o peso de cada nó.
Implementação de Graph em Java
O programa a seguir mostra a implementação de um gráfico em Java. Aqui, usamos a lista de adjacências para representar o grafo.
import java.util.*; //class to store edges of the weighted graph class Edge { int src, dest, weight; Edge(int src, int dest, int weight) { this.src = src; this.dest = dest; this.weight = weight; } } // Graph class class Graph { // node of adjacency list static class Node { int value, weight; Node(int value, int weight) { this.value = value; this.weight = weight; } }; // define adjacency list List adj_list = new ArrayList(); //Graph Constructor public Graph(List edges) { // adjacency list memory allocation for (int i = 0; i Resultado:
Graph Traversal Java
Para realizar qualquer ação significativa, como procurar a presença de quaisquer dados, precisamos percorrer o gráfico de forma que cada vértice e a borda do gráfico sejam visitados pelo menos uma vez. Isso é feito usando algoritmos de gráfico que nada mais são do que um conjunto de instruções que nos ajudam a percorrer o gráfico.
Existem dois algoritmos com suporte para percorrer o gráfico em Java .
- Travessia em profundidade
- Travessia em largura
Traversal em profundidade
A pesquisa em profundidade (DFS) é uma técnica usada para percorrer uma árvore ou um gráfico. A técnica DFS começa com um nó raiz e então atravessa os nós adjacentes do nó raiz indo mais fundo no gráfico. Na técnica DFS, os nós são percorridos em profundidade até que não haja mais filhos para explorar.
Uma vez que alcançamos o nó folha (não há mais nós filhos), o DFS retrocede e começa com outros nós e realiza a travessia de maneira semelhante. A técnica DFS usa uma estrutura de dados de pilha para armazenar os nós que estão sendo percorridos.
A seguir está o algoritmo para a técnica DFS.
Algoritmo
Etapa 1: comece com o nó raiz e insira-o na pilha
Etapa 2: Retire o item da pilha e insira-o na lista de 'visitados'
Etapa 3: para o nó marcado como 'visitado' (ou na lista de visitantes), adicione os nós adjacentes deste nó que ainda não foram marcados como visitados à pilha.
Etapa 4: Repita as etapas 2 e 3 até que a pilha esteja vazia.
Ilustração da técnica DFS
Agora vamos ilustrar a técnica DFS usando um exemplo apropriado de um gráfico.
A seguir está um gráfico de exemplo. Mantemos pilha para armazenar os nós explorados e uma lista para armazenar os nós visitados.
Começaremos com A, marcá-lo como visitado e adicioná-lo à lista de visitados. Em seguida, consideraremos todos os nós adjacentes de A e colocaremos esses nós na pilha como mostrado abaixo.
Em seguida, retiramos um nó da pilha, ou seja, B e o marcamos como visitado. Em seguida, o adicionamos à lista 'visitados'. Isso é representado abaixo.
Agora consideramos os nós adjacentes de B que são A e C. Desse ponto A já foi visitado. Então, nós o ignoramos. Em seguida, retiramos C da pilha. Marque C como visitado. O nó adjacente de C, ou seja, E, é adicionado à pilha.
Em seguida, retiramos o próximo nó E da pilha e o marcamos como visitado. O nó adjacente do Nó E é C que já foi visitado. Então, nós o ignoramos.
ver meu site em diferentes navegadores
Agora, apenas o nó D permanece na pilha. Portanto, marcamos como visitado. Seu nó adjacente é A que já foi visitado. Portanto, não o adicionamos à pilha.
Neste ponto, a pilha está vazia. Isso significa que completamos o percurso em profundidade para o gráfico fornecido.
A lista visitada fornece a sequência final de travessia usando a técnica de profundidade primeiro. A seqüência DFS final para o gráfico acima é A-> B-> C-> E-> D.
Implementação DFS
import java.io.*; import java.util.*; //DFS Technique for undirected graph class Graph { private int Vertices; // No. of vertices // adjacency list declaration private LinkedList adj_list(); // graph Constructor: to initialize adjacency lists as per no of vertices Graph(int v) { Vertices = v; adj_list = new LinkedList(v); for (int i=0; i Resultado:
Aplicações de DFS
# 1) Detectar um ciclo em um gráfico: O DFS facilita a detecção de um ciclo em um gráfico quando podemos retroceder até uma borda.
# 2) Pathfinding: Como já vimos na ilustração DFS, dados quaisquer dois vértices, podemos encontrar o caminho entre esses dois vértices.
# 3) Mínimo árvore de abrangência e caminho mais curto: Se executarmos a técnica DFS no gráfico não ponderado, ela nos fornecerá a árvore de abrangência mínima e o caminho em curto.
# 4) Classificação topológica: A classificação topológica é usada quando precisamos agendar os trabalhos. Temos dependências entre vários empregos. Também podemos usar classificação topológica para resolver dependências entre linkers, planejadores de instrução, serialização de dados, etc.
Traversal em largura
A técnica de amplitude (BFS) usa uma fila para armazenar os nós do gráfico. Em comparação com a técnica DFS, no BFS percorremos a amplitude do gráfico. Isso significa que percorremos o nível do gráfico. Quando exploramos todos os vértices ou nós em um nível, passamos para o próximo nível.
A seguir está um algoritmo para a técnica de travessia em largura .
Algoritmo
Vamos ver o algoritmo da técnica BFS.
Dado um gráfico G para o qual precisamos executar a técnica BFS.
- Passo 1: Comece com o nó raiz e insira-o na fila.
- Passo 2: Repita as etapas 3 e 4 para todos os nós do gráfico.
- Etapa 3: Remova o nó raiz da fila e inclua-o na lista Visitados.
- Passo 4: Agora adicione todos os nós adjacentes do nó raiz à fila e repita as etapas 2 a 4 para cada nó. (FIM DO LOOP)
- Etapa 6: SAÍDA
Ilustração de BFS
Vamos ilustrar a técnica BFS usando um gráfico de exemplo mostrado abaixo. Observe que mantemos uma lista chamada ‘Visitados’ e uma fila. Usamos o mesmo gráfico que usamos no exemplo DFS para fins de clareza.
Primeiro, começamos com a raiz, ou seja, o nó A e o adicionamos à lista visitada. Todos os nós adjacentes do nó A, isto é, B, C e D, são adicionados à fila.
Em seguida, removemos o nó B da fila. Nós o adicionamos à lista de Visitados e marcamos como visitado. Em seguida, exploramos os nós adjacentes de B na fila (C já está na fila). Outro nó adjacente A já foi visitado, portanto, o ignoramos.
Em seguida, removemos o nó C da fila e o marcamos como visitado. Adicionamos C à lista visitada e seu nó adjacente E é adicionado à fila.
Em seguida, excluímos D da fila e o marcamos como visitado. O nó adjacente A do Nó D já foi visitado, então nós o ignoramos.
Portanto, agora apenas o nó E está na fila. Marcamos como visitado e o adicionamos à lista de visitados. O nó adjacente de E é C que já foi visitado. Portanto, ignore.
Neste ponto, a fila está vazia e a lista visitada possui a sequência que obtivemos como resultado da travessia BFS. A sequência é, A-> B-> C-> D-> E.
Implementação BFS
O seguinte programa Java mostra a implementação da técnica BFS.
import java.io.*; import java.util.*; //undirected graph represented using adjacency list. class Graph { private int Vertices; // No. of vertices private LinkedList adj_list(); //Adjacency Lists // graph Constructor:number of vertices in graph are passed Graph(int v) { Vertices = v; adj_list = new LinkedList(v); for (int i=0; i Resultado:
Aplicações de BFS Traversal
# 1) Coleta de lixo: Um dos algoritmos usados pela técnica de coleta de lixo para copiar a coleta de lixo é o “algoritmo de Cheney”. Este algoritmo usa uma técnica de travessia em largura.
# 2) Transmissão em redes: A transmissão de pacotes de um ponto a outro em uma rede é feita usando a técnica BFS.
# 3) Navegação GPS: Podemos usar a técnica BFS para encontrar nós adjacentes enquanto navegamos usando GPS.
# 4) Sites de redes sociais: A técnica BFS também é usada em sites de redes sociais para encontrar a rede de pessoas ao redor de uma pessoa específica.
# 5) Caminho mais curto e árvore de abrangência mínima no gráfico não ponderado: No gráfico não ponderado, a técnica BFS pode ser usada para encontrar uma árvore de abrangência mínima e o caminho mais curto entre os nós.
Biblioteca Java Graph
Java não torna obrigatório para os programadores sempre implementarem os gráficos no programa. Java fornece muitas bibliotecas prontas que podem ser usadas diretamente para fazer uso de gráficos no programa. Essas bibliotecas têm toda a funcionalidade de API de gráfico necessária para fazer uso completo do gráfico e seus vários recursos.
A seguir, é fornecida uma breve introdução a algumas das bibliotecas de gráficos em Java.
# 1) Google Guava: O Google Guava fornece uma biblioteca rica que oferece suporte a gráficos e algoritmos, incluindo gráficos simples, redes, gráficos de valor etc.
# 2) Apache Commons: Apache Commons é um projeto Apache que fornece componentes de estrutura de dados de gráfico e APIs que possuem algoritmos que operam nessa estrutura de dados de gráfico. Esses componentes são reutilizáveis.
# 3) JGraphT: JGraphT é uma das bibliotecas de gráficos Java amplamente utilizadas. Ele fornece funcionalidade de estrutura de dados de gráfico contendo gráfico simples, gráfico direcionado, gráfico ponderado, etc., bem como algoritmos e APIs que funcionam na estrutura de dados de gráfico.
# 4) SourceForge JUNG: JUNG significa “Java Universal Network / Graph” e é uma estrutura Java. JUNG fornece uma linguagem extensível para análise, visualização e modelagem dos dados que queremos representar em um gráfico.
A JUNG também fornece vários algoritmos e rotinas para decomposição, agrupamento, otimização, etc.
perguntas frequentes
Q # 1) O que é um gráfico em Java?
Responda: Uma estrutura de dados de gráfico armazena principalmente dados conectados, por exemplo, uma rede de pessoas ou uma rede de cidades. Uma estrutura de dados de gráfico normalmente consiste em nós ou pontos chamados vértices. Cada vértice é conectado a outro vértice usando links chamados arestas.
Q # 2) Quais são os tipos de gráficos?
Responda: Diferentes tipos de gráficos estão listados abaixo.
- Gráfico de linha: Um gráfico de linha é usado para traçar as mudanças em uma propriedade particular em relação ao tempo.
- Gráfico de barras: Os gráficos de barras comparam valores numéricos de entidades como a população em várias cidades, porcentagens de alfabetização em todo o país, etc.
Além desses tipos principais, também temos outros tipos, como pictograma, histograma, gráfico de área, gráfico de dispersão, etc.
Q # 3) O que é um gráfico conectado?
Responda: Um grafo conectado é um grafo no qual cada vértice está conectado a outro vértice. Portanto, no gráfico conectado, podemos chegar a todos os vértices de todos os outros vértices.
Q # 4) Quais são as aplicações do gráfico?
perguntas e respostas da entrevista pl / sql
Responda: Os gráficos são usados em uma variedade de aplicações. O gráfico pode ser usado para representar uma rede complexa. Os gráficos também são usados em aplicativos de rede social para denotar a rede de pessoas, bem como para aplicativos como localizar pessoas ou conexões adjacentes.
Os gráficos são usados para denotar o fluxo de computação na ciência da computação.
Q # 5) Como você armazena um gráfico?
Resposta: Existem três maneiras de armazenar um gráfico na memória:
# 1) Podemos armazenar nós ou vértices como objetos e arestas como ponteiros.
#dois) Também podemos armazenar grafos como matrizes de adjacência cujas linhas e colunas são iguais ao número de vértices. A interseção de cada linha e coluna denota a presença ou ausência de uma aresta. No gráfico não ponderado, a presença de uma aresta é denotada por 1, enquanto no gráfico ponderado é substituída pelo peso da aresta.
# 3) A última abordagem para armazenar um grafo é usar uma lista de adjacência de arestas entre vértices ou nós do grafo. Cada nó ou vértice possui sua lista de adjacências.
Conclusão
Neste tutorial, discutimos os gráficos em Java em detalhes. Exploramos os vários tipos de gráficos, implementação de gráficos e técnicas de travessia. Os gráficos podem ser usados para encontrar o caminho mais curto entre os nós.
Em nossos próximos tutoriais, continuaremos a explorar os gráficos, discutindo algumas maneiras de encontrar o caminho mais curto.
=> Veja a série de treinamento simples em Java aqui.
Leitura recomendada
- Tutorial de reflexão Java com exemplos
- Como implementar o algoritmo de Dijkstra em Java
- Tutorial Java SWING: Container, Componentes e Manipulação de Eventos
- Tutorial de JAVA para iniciantes: mais de 100 tutoriais práticos em vídeo Java
- TreeMap em Java - Tutorial com exemplos de TreeMap em Java
- Modificadores de acesso em Java - Tutorial com exemplos
- Tutorial Java String com String Buffer e String Builder
- Java String contains () Tutorial de método com exemplos
