Estou tentando implementar um grafo em java, como não sou muito fera em programação estou enfrentando algumas dificuldades. Revirei a net e achei alguns exemplos. Bom com o que eu achei fiz três classes.
A classe vértice
[code]public class Vertice {
private String rotulo;
private int peso;
int nome;
public Vertice() {
super();
}
public String getRotulo() {
return rotulo;
}
public void setRotulo(String rotulo) {
this.rotulo = rotulo;
}
public int getPeso() {
return peso;
}
public void setPeso(int peso) {
this.peso = peso;
}
}
[/code]
A classe aresta
public class Aresta {
private String rotulo;
private Vertice v1;
private Vertice v2;
private int peso;
public Aresta(Vertice v1, Vertice v2) {
super();
this.v1 = v1;
this.v2 = v2;
}
public String getRotulo() {
return rotulo;
}
public void setRotulo(String rotulo) {
this.rotulo = rotulo;
}
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;
}
public int getPeso() {
return peso;
}
public void setPeso(int peso) {
this.peso = peso;
}
public boolean contemAresta(Vertice v1,Vertice v2){
if((this.v1 == v1)&&(this.v2 == v2))
return(true);
if((this.v1 == v2)&&(this.v2 == v1))
return(true);
return(false);
}
public boolean contemVertice(Vertice v){
if(this.v1 == v)
return(true);
if(this.v2 == v)
return(true);
return(false);
}
}e a classe grafo
import java.util.ArrayList;
public class Grafo {
private ArrayList arestas;
private ArrayList vertices;
private int [][]matrizAdjacencia;
private int [][] matrizIncidencia;
private boolean isOrientado;
// Cria um grafo usando matriz de adjacencia
public Grafo(int[][] matrizAdjacencias){
vertices = new ArrayList();
arestas = new ArrayList();
this.isOrientado = false;
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();
v.nome = this.getNovoNome();
v.setRotulo(v.nome+"");
vertices.add(v);
this.updateMatrizAdjacencias();
this.updateMatrizIncidencias();
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 int getNovoNome(){
return(vertices.size()+1);
}
public Vertice getVertice(int i){
return((Vertice)vertices.get(i));
}
public synchronized Aresta getAresta(int i){
return((Aresta)arestas.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);
}
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 synchronized int getQtdVertices(){
return(vertices.size());
}
public void imprimeGrafo(Grafo grafo){
int i, j;
System.out.println(" ");
for(i=0; i<=(getQtdVertices()-1);i++){
System.out.println(i);
System.out.println("\n");
for(i=0; i<=(getQtdVertices()-1);i++){
System.out.println(i);
for(j=0; j<=(getQtdVertices()-1);j++){
System.out.println(matrizAdjacencia[i][j]);
System.out.println(matrizIncidencia[i][j]);
}
}
}
}
}
Bom os metodos da classe grafo eu copiei e gostaria que alguém me explicasse como funciona. Porque naum entendi muito bem.
