Grafos

31 de março de 2009 2 respostas

JulianaSouza 31 de março de 2009

To fazendo um trabalho de grafos e to precisando de ajuda

Queria saber como criar uma matriz de adjacencia
Eu sei como ela funciona
Mas eu tenho que criar um metodo?
Fazer um construtor?

public class Aresta {
	private Vertice v1;
	private Vertice v2;
	
	public Aresta(Vertice v1, Vertice v2) {
		super();
		this.v1 = v1;
		this.v2 = v2;
	}
	public Aresta() {
		super();
		
	}
	public Vertice getV1() {
		return v1;
	}
	public void setV1(Vertice v1) {
		this.v1 = v1;
	}
	public Vertice getV2() {
		return v2;
	}
	public void setV2(Vertice v2) {
		this.v2 = v2;
	}
	

}

import java.util.ArrayList;


public class Grafo {

	private ArrayList arestas;
	private ArrayList vertices;
	private int [][]matrizAdjacencia;

	public Grafo() {
		vertices = new ArrayList();
        arestas = new ArrayList();
	}
	
	
	public Vertice addVertice(char nome){
		Vertice v = new Vertice();
		vertices.add(v);
		return v;

	

	

	}
	public int getQtdVertices(){
		return(vertices.size());
	}
}

public class Principal {


	public static void main(String[] args) {

		Grafo grafo = new Grafo();
		grafo.addVertice('A');
		grafo.addVertice('B');
		grafo.addVertice('C');
		grafo.addVertice('D');
		grafo.addVertice('E');
		grafo.addVertice('F');
		
		



		System.out.println(grafo.getQtdVertices());

	}

}

public class Vertice {
	
	char nome;
	
	public Vertice(char nome) {
		super();
		this.nome = nome;
	}

	public Vertice() {
		super();
		
	}


	public char getNome() {
		return nome;
	}

	public void setNome(char nome) {
		this.nome = nome;
	}

	
}

2 Respostas

JulianaSouza 31 de mar. de 2009

já consegui implementar a matriz

agora não to conseguindo adicionar as arestas

nçao sei se to fazendo o main errado ou se o metodo é que tá errado alguém pode dar uma olhada pra mim

import java.util.ArrayList;


public class Grafo {

	private ArrayList arestas;
	private ArrayList vertices;
	private int [][]matrizAdjacencia;
	private int [][]matrizIncidencia;

	public Grafo() {
		vertices = new ArrayList();
		arestas = new ArrayList();
	}
	public Grafo(int[][] matrizAdjacencias){
		vertices = new ArrayList();
		arestas = new ArrayList();

		for (int i=0;i<matrizAdjacencias.length;i++) {
			this.addVertice( );
		}
		for (int i=0;i<matrizAdjacencias.length;i++) {
			for (int j=0;j<matrizAdjacencias.length;j++) {
				if(matrizAdjacencias[i][j]==1){
					Vertice v1 = this.getVertice(i);
					Vertice v2 = this.getVertice(j);
					this.addAresta(v1,v2);
				}
			}
		}
	}




	public Vertice addVertice(){
		Vertice v = new Vertice();
		vertices.add(v);
		return v;
	}
	public  Aresta addAresta(Vertice _v1, Vertice _v2){
		if(this.getArestaEntreVertices(_v1,_v2)==null){
			Aresta aresta = new Aresta(_v1,_v2);
			arestas.add(aresta);

			this.updateMatrizAdjacencias();
			this.updateMatrizIncidencias();
			return(aresta);
		}
		return(null);
	}
	public Aresta getArestaEntreVertices(Vertice _v1, Vertice _v2){
		Aresta aresta;
		for(int i=0;i<arestas.size();i++){
			aresta = this.getAresta(i);
			if(aresta.contemAresta(_v1,_v2)) 
				return(aresta);
		}
		return(null);
	}
	
	private  void updateMatrizAdjacencias(){
		Vertice vertice;
		Vertice verticeAux;
		ArrayList v_adjacencias;
		matrizAdjacencia = new int[vertices.size()][vertices.size()];


		for(int i=0;i<vertices.size();i++){
			vertice = this.getVertice(i);
			v_adjacencias = this.getAdjacencias(vertice);
			for(int j=0;j<v_adjacencias.size();j++){
				verticeAux = (Vertice)v_adjacencias.get(j);
				matrizAdjacencia[i][verticeAux.nome-1] = 1;
			}
		}
	}
	private  void updateMatrizIncidencias(){
		Aresta aresta;
		matrizIncidencia = new int[vertices.size()][arestas.size()];

		for(int j=0;j<arestas.size();j++){
			aresta = this.getAresta(j);
			matrizIncidencia[aresta.getV1().nome-1][j] = 1;
			matrizIncidencia[aresta.getV2().nome-1][j] = 1;
		}
	}

	public  Aresta getAresta(int i){
		return((Aresta)arestas.get(i));
	}
	

	public  Vertice getVertice(int i){
		return((Vertice)vertices.get(i));
	}


	public ArrayList getAdjacencias(Vertice v){
		Aresta aresta;
		ArrayList adjacencias = new ArrayList();
		for(int i=0;i<arestas.size();i++){
			aresta = this.getAresta(i);
			if(aresta.getV1() == v){
				adjacencias.add(aresta.getV2());
			}
			if(aresta.getV2() == v){
				adjacencias.add(aresta.getV1());
			}
		}

		return(adjacencias);
	}

	public int getQtdVertices(){
		return(vertices.size());
	}
}

tnaires 31 de mar. de 2009

Usuário duplicado?
http://www.guj.com.br/posts/list/122406.java
http://www.guj.com.br/posts/list/122482.java
Cara, não precisa fazer isso…

Criado 31 de março de 2009

Ultima resposta 31 de mar. de 2009

Respostas 2

Participantes 2

2 Respostas

Topicos relacionados