Grafos ponderados - Grafos

Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar.

A partir de agora, reserve sua mente para um novo conceito. Pegue tudo o que você já aprendeu e guarde, pois será necessário. Você está prestes a conhecer um novo tipo de grafo, com novas características e ferramentas. Conheça os Grafos Ponderados.

Resumidamente, grafos ponderados são grafos com pesos em suas arestas (Figura 1). Entenda pesos como valores e não como quilos. São utilizados para determinar qual o melhor trajeto adotar dado o problema. Pense na seguinte situação: você quer sair do centro da cidade do Rio de Janeiro e chegar no Cristo Redentor. Como chegar lá ? Existem vários caminhos. Qual deles é o melhor ? Isso depende de você. Se está com pressa por causa de tempo, talvez aquele caminho mais curto porém mais perigoso seja melhor do que aquele mais seguro e longo, ou talvez se um trajeto com mais paisagens for mais importante do que rapidez, um outro caminho pode ser o ideal. Visto que podem existir diversas possibilidades de caminhos a serem feitos, um critério de escolha deve ser escolhido e em cima dele as diversas arestas que conectam o ponto A ao ponto B ganharão seus respectivos pesos.

Figura 1 - Diferenças entre um grafo ponderado e não ponderado

Um grafo ponderado pode ser tanto orientado quanto não orientado (Figura 2) e essa orientação é a mesma já vista anteriormente, logo os problemas que essa característica traz também são os mesmos e obviamente acabam se acumulando com os novos desafios oriundos das arestas ponderadas. Estruturas como matrizes ou listas de adjacências também aparecem aqui, logo nenhuma surpresa quanto a isso. O que realmente vai diferenciar este tipo de grafo são seus pesos em suas arestas e os algoritmos originados a partir da análise dos mesmos. Tais diferenciais tornam a implementação um pouco diferente do que já estávamos acostumado.

Figura 2 - Diferenças entre um grafo ponderado orientado e um não orientado

WeightedGraph.java

	public class WeightedGraph {
	private final int MAX_VERTEX = 10;
	private Vertex[] vertexs;
	private Edge[][] adjacencyMatrix;
	private int currentAmountOfVerxtes;
	public WeightedGraph(){
	this.vertexs = new Vertex[MAX_VERTEX];
	adjacencyMatrix = new Edge[MAX_VERTEX][MAX_VERTEX];
	currentAmountOfVerxtes = 0;
	}
	public void addVertex(char label){
	vertexs[currentAmountOfVerxtes++] = new Vertex(label);
	}
	public void addEdgeNonOriented(int start, int end, int weight){
	Vertex vertexStart = vertexs[start];
	Vertex vertexEnd = vertexs[end];
	adjacencyMatrix[start][end] = new Edge(vertexStart, vertexEnd, weight);
	adjacencyMatrix[end][start] = new Edge(vertexEnd, vertexStart, weight);
	}
	public void displayGraph(){
	for(int i=0; i<adjacencyMatrix.length; i++){
	for(int j=0; j<adjacencyMatrix[i].length; j++){
	Edge edge = adjacencyMatrix[i][j];
	if(edge != null){
	System.out.println(edge.getVertexBegin().getLabel() + " - " + edge.getVertexEnd().getLabel() + ": " + edge.getWeight());
	}
	}
	}
	}
	}

view raw WeightedGraph.java hosted with ❤ by GitHub

Como dito antes, alguns métodos não são lá uma surpresa, contudo alguns destaques podem ser feitos. Note que não existe inicialização com 0’s da matriz de adjacência aqui, pois ela não é mais uma matriz de inteiros e sim de objetos do tipo Edge. Como é de conhecimento de todos, variáveis de instância em Java tem seu valor default como null, logo automaticamente a matriz tem valores nulos em todas as suas posições e isso é o bastante para saber se existe uma aresta ali ou não.

O método de adição de aresta deixa claro através de seu nome que são arestas não orientadas que são adicionadas e ele recebe como parâmetro o peso da aresta. Realizei a mudança no nome com a finalidade de deixar o código mais intuitivo. Lembre-se que pelo fato das arestas não serem orientadas é preciso marcar a matriz duas vezes e que agora será inserido um objeto do tipo Edge ao invés de um inteiro. O resto da classe é mais do mesmo que já estamos acostumados.

Edge.java

	public class Edge {
	private Vertex vertexBegin;
	private Vertex vertexEnd;
	private int weight;
	public Edge(Vertex vertexBegin, Vertex vertexEnd, int weight){
	this.vertexBegin = vertexBegin;
	this.vertexEnd = vertexEnd;
	this.weight = weight;
	}
	public Vertex getVertexBegin(){
	return this.vertexBegin;
	}
	public Vertex getVertexEnd(){
	return this.vertexEnd;
	}
	public int getWeight(){
	return this.weight;
	}
	}

view raw Edge.java hosted with ❤ by GitHub

Esta classe representa uma aresta, podendo ser orientada ou não, de um grafo ponderado. Lembre-se que a orientação é ditada na matriz. Dentro dela estão todas as informações necessárias de uma aresta, como: vértice de origem, destino e seu peso.

WeightedGraphApp.java

	public class WeightedGraphApp {
	public static void main(String[] args) {
	WeightedGraph weightedGraph = new WeightedGraph();
	weightedGraph.addVertex('A');
	weightedGraph.addVertex('B');
	weightedGraph.addVertex('C');
	weightedGraph.addVertex('D');
	weightedGraph.addVertex('E');
	weightedGraph.addEdgeNonOriented(0,3,4); //A-D: 4
	weightedGraph.addEdgeNonOriented(0,4,3); //A-E: 3
	weightedGraph.addEdgeNonOriented(0,2,10); //A-C: 10
	weightedGraph.addEdgeNonOriented(1,3,7); //B-D: 7
	weightedGraph.addEdgeNonOriented(1,2,1); //B-C: 1
	weightedGraph.displayGraph();
	}
	}

view raw WeightedGraphApp.java hosted with ❤ by GitHub

Classe cliente, tendo como responsabilidades a criação e exibição de um grafo ponderado.

Com isso, chegamos ao fim de mais uma postagem.

Estamos chegando ao fim da série Grafos. Faltam somente mais alguns assuntos para encerramento total desta série, não perca nenhum deles. Após esta série de assuntos começaremos uma nova com um novo formato que ainda é surpresa para tornar a nossa experiência a mais dinâmica possível.

Até a próxima minha boa gente ! 😘

Leia nossa postagem anterior: Indicações de livros - Estruturas de dados e Algoritmos em Java

Download do código-fonte
Link do repositório GitHub: https://github.com/PrecisoEstudarSempre/Graphs.git

Dúvidas !? Sugestões ?! Críticas ou elogios ?!

Deixe aí nos comentários, envie um e-mail ou uma mensagem na nossa página do Facebook.

E-mail: precisoestudarsempre@gmail.com
Facebook: https://www.facebook.com/precisoestudarsempre/
Canal Preciso Estudar Sempre: https://www.youtube.com/channel/UCUoW8dS38rXr0a5jWU57etA