Alguem entende de grafos

Programação Java
#1

Presciso implementar um grafo com lista de adjacencia
alguem pode me ajudar a começar…

quais são as classes que presciso
o que elas fazem
ja reviresi a net e não achei muita coisa concreta

#2

Será que alguém pode me ajudar

#3

Olá
Imagine que você tem o seguinte grafo:

A - C | B - D
Nele, C e B são vizinhos de A e A e D são vizinhos de C.

Você representa esse grafo usando lista de adjacências da seguinte forma:

  • Crie um array cuja quantidade de elementos é igual à quantidade de nós do grafo;
  • Cada elemento do array é uma lista que contém os seus vizinhos.

Então, a lista de adjacências para o grafo acima ficaria:

A -> B -> C
B -> A -> D
C
D

Tem muito material na internet disponível, sinceramente não sei como você não encontrou nada. Tentou buscar no google por lista de adjacências?

#4

Opa.

V se te ajuda… ja tem uns post no Guj.

http://www.guj.com.br/posts/list/41025.java

http://www.guj.com.br/posts/list/41023.java

http://www.ime.usp.br/~pf/algoritmos_em_grafos/index.html

#5

[quote=henrique.guimaraes]Será que alguém pode me ajudar
[/quote]
Outra coisa, tenha mais paciência ao postar uma dúvida que alguém logo responderá.

#6

Desculpa
é que eu tava ancioso

#7

Bom eu tava tentando mplementar a matriz de adjacencia e incidencia, mas acho que tava no caminho errado
vou postar as classes[code]
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);
}

}
[/code][code]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 vazio
    **/
    public Grafo(){
        vertices = new ArrayList();
        arestas = new ArrayList();
        this.isOrientado=false;
    }

// 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());
}

}

[/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]
public class Main {

public static void main(String[] args) {

	Grafo grafo = new Grafo();
	grafo.addVertice();


}

}

[/code]

#8

Bom as classes acima eu montei copiando algumas coisas da net
a princiio parecia que ia dar certo
mas acho que tenho que rever alguns metodos
por exemplo eu quero adicionar os vertices e arestas e quero que o programa retorne a matriz de adjacencia e a de incidencia

#9