Bom dia a todos.
Estou tentando umplementar um código Java e estou apanhando.
Não quero que ninguém faça o exercício pra mim.
Gostaria de algum exemplo simples de como implementar um grafo por lista de adjacência ou matriz de adjacência.
Não estou saindo do chão e algum exemplo seria de boa valia.
Obrigado a todos e ressalto que não quero que façam meu exercício. 
Da uma olhada no livro de estrutura de dados do Thomas Cormen,
ele mostra grafos e tem pseudo-código dos algoritmos para
você conseguir começar.
Vou postar o que tenho até agora Senhores:
String vertices[] = {"0","1","2","3","4"};
String inicio = "2";
String arestas[][] = { {"0","1","0","0","0"}, {"1","0","1","1","0"}, {"0","1","0","0","1"}, {"0","1","0","0","0"}, {"0","0","1","0","0"}};
Acredito estar no caminho.
Agora eu preciso fazer o que para poder realizar Buscas por Profundidade e Largura?
Algum exemplo seria ótimo (mas não quero que façam o exercício, ninguém faz isso)
Obrigado
[quote=marcosharbs]Da uma olhada no livro de estrutura de dados do Thomas Cormen,
ele mostra grafos e tem pseudo-código dos algoritmos para
você conseguir começar.[/quote]
Vou buscar.
Obrigado.
achei meio estranha sua matriz de adjacência
o conceito de matriz de adjacência em grafos é um
array bidimensional n x n onde n é o número de vértices do seu grafo
e se possui uma aresta entre n1 e n2 por exemplo a posição
da matriz que conincidirem a linha e a coluna você coloca 1
e se não tiver aresta você coloca 0, um exemplo abaixo de um grafo
com 3 vértices:
int matriz_adjacencia[][] = {{0, 1, 0},
{0, 0, 1},
{0, 0, 0}};Nesse exemplo acima o grafo possui uma aresta entre os vértices v2 e v1 e outra entre os vértices v3 e v2.
[quote=marcosharbs]achei meio estranha sua matriz de adjacência
o conceito de matriz de adjacência em grafos é um
array bidimensional n x n onde n é o número de vértices do seu grafo
e se possui uma aresta entre n1 e n2 por exemplo a posição
da matriz que conincidirem a linha e a coluna você coloca 1
e se não tiver aresta você coloca 0, um exemplo abaixo de um grafo
com 3 vértices:
int matriz_adjacencia[][] = {{0, 1, 0},
{0, 0, 1},
{0, 0, 0}};Nesse exemplo acima o grafo possui uma aresta entre os vértices v2 e v1 e outra entre os vértices v3 e v2.[/quote]
Justamente o que eu fiz:
String arestas[][] = { {"0","1","0","0","0"},
{"1","0","1","1","0"},
{"0","1","0","0","1"},
{"0","1","0","0","0"},
{"0","0","1","0","0"}
};
Vou dar uma olhada no livro e posto aqui alguma coisa.
Se alguém tiver algum exemplo será bem vindo.
[quote=alangaro.si@gmail.com][quote=marcosharbs]achei meio estranha sua matriz de adjacência
o conceito de matriz de adjacência em grafos é um
array bidimensional n x n onde n é o número de vértices do seu grafo
e se possui uma aresta entre n1 e n2 por exemplo a posição
da matriz que conincidirem a linha e a coluna você coloca 1
e se não tiver aresta você coloca 0, um exemplo abaixo de um grafo
com 3 vértices:
int matriz_adjacencia[][] = {{0, 1, 0},
{0, 0, 1},
{0, 0, 0}};Nesse exemplo acima o grafo possui uma aresta entre os vértices v2 e v1 e outra entre os vértices v3 e v2.[/quote]
Justamente o que eu fiz:
String arestas[][] = { {"0","1","0","0","0"},
{"1","0","1","1","0"},
{"0","1","0","0","1"},
{"0","1","0","0","0"},
{"0","0","1","0","0"}
};
Vou dar uma olhada no livro e posto aqui alguma coisa.
Se alguém tiver algum exemplo será bem vindo.
[/quote]
Verdade olhei e achei que era o número dos vértices ali.
Agora que tenho a Matriz de Adjacências, teoricamente seria só implementar um pseudo algoritmo não é verdade?
Ou tem algo mais que eu precise saber? Algo relacionado a árvores talvez?
[quote=alangaro.si@gmail.com]Agora que tenho a Matriz de Adjacências, teoricamente seria só implementar um pseudo algoritmo não é verdade?
Ou tem algo mais que eu precise saber? Algo relacionado a árvores talvez?
[/quote]
Teoricamente é isso.
Uma árvore na verdade é um grafo, um tipo especial de grafo
que não possui ciclos.
E se você implementar uma busca em profundidade o algoritmo
vai gerar uma árvore de busca.
Boa noite a todos novamente.
Vou postar o código que fiz até agora.
Se puderem me ajudar (mas não fazer o exercício).
Preciso fazer busca por largura e busca por profundidade.
O código é composto de três classes:
Classe Aresta
public class Aresta {
private No de;
private No para;
public Aresta(No de, No para){
this.de = de;
this.para = para;
}
public No getDe() {
return de;
}
public void setDe(No de) {
this.de = de;
}
public No getPara() {
return para;
}
public void setPara(No para) {
this.para = para;
}
}Classe No
import java.util.Collections;
import java.util.Set;
public class No {
private String descricao;
private Set<Aresta> arestas;
public No(String descricao){
this.descricao = descricao;
}
public Boolean addAresta(No para){
return arestas.add(new Aresta(this, para));
}
public Set<Aresta> getArestas(){
return Collections.unmodifiableSet(arestas);
}
public String getDescricao(){
return descricao;
}
}Classe Main
public class Main {
public static void main(String[] args){
No no1 = new No("no1");
No no2 = new No("no2");
No no3 = new No("no3");
No no4 = new No("no4");
No no5 = new No("no5");
no1.addAresta(no2);
no1.addAresta(no3);
no2.addAresta(no3);
no2.addAresta(no4);
no3.addAresta(no4);
no3.addAresta(no5);
no4.addAresta(no5);
}
}Se alguem puder postar um exemplo eu agradeço