Tenho uma dúvida bem básica!
Mas ta complicadinha pra mim.
Preciso fazer uma lista de adjacência. Mas a minha dúvida, seria em como fazer um vetor, e depois, ter valores de uma lista em algum número desse vetor.
Por exemplo: um vetor de 10 posições; cada posição terá uma lista encadeada (acho que quem sabe lista adjacencia vai entender bem que é essa ideia que to passando)
vetor1-> lista com numeros 1-> 2 3
vetor2-> … 2-> 1
vetor3-> 3->2
…
Como faço pra fazer um vetor com essas listas em java?
você quer fazer uma matriz?
marinagtto,
Entendi que você quer fazer uma lista de adjacência conforme descrito na wikipedia:
http://pt.wikipedia.org/wiki/Lista_de_adjac%C3%AAncia
Não achei a dúvida tão básica, mas acho que dá para resolver da seguinte forma:
A classe abaixo eu peguei da implementação em Java de uma Lista Ligada, que tem na Wikipedia. Só acrescentei o método listar.
[code]class No
{
Object elemento;
No prox;
No (Object elem){
elemento = elem;
prox = null;
}
}
public class ListaLigada
{
private No primeiro, ultimo;
private int nroNos;
ListaLigada ()
{
primeiro = null;
ultimo = null;
nroNos = 0;
}
public boolean isVazia() {
return (primeiro == null && ultimo == null);
}
public void addInicio(Object o) {
nroNos++;
No novoNo = new No(o);
if (isVazia())
ultimo = novoNo;
else
novoNo.prox = primeiro;
primeiro = novoNo;
}
public void addFinal(Object o) {
nroNos++;
No novoNo = new No(o);
if (isVazia())
primeiro = novoNo;
else
ultimo.prox = novoNo;
ultimo = novoNo;
}
public int getNroNos() {
return nroNos;
}
/*
* @param posicao
* posição contada a partir do zero como primeiro elemento
*/
public void addMeio(Object o, int posicao) {
nroNos++;
No novoNo = new No(o);
if(posicao <= 1) {
addInicio(novoNo);
return;
}
if (posicao > nroNos) {
//Outra abordagem seria lançar exceção para posição inválida (>nroNos+1)
addFinal(novoNo);
return;
}
No noTemp = primeiro.prox;
for(int posAux=1;posAux<posicao;posAux++)
noTemp = noTemp.prox;
novoNo.prox = (noTemp.prox).prox;
noTemp.prox = novoNo;
}
public void Remover(Object elemento)
{
No noTemp = primeiro;
No noAnt = null;
if (primeiro.elemento.equals(elemento)) {
primeiro = primeiro.prox;
nroNos--;
}
else {
while (noTemp !=null && !noTemp.elemento.equals(elemento)) {
noAnt = noTemp;
noTemp = noTemp.prox;
}
if(noTemp != null) {
noAnt.prox = noTemp.prox;
nroNos--;
}
if(noTemp == ultimo) {
ultimo = noAnt;
}
}
}
public Object BuscarElemento (Object elemento)
{
int i = 1;
No noTemp = primeiro;
while (noTemp !=null) {
if(noTemp.elemento.equals(elemento)) {
return noTemp;
}
i = i +1;
noTemp = noTemp.prox;
}
return null;
}
public void listar(){
No noTemp = primeiro;
while (noTemp !=null) {
System.out.println(noTemp.elemento.toString());
noTemp = noTemp.prox;
}
}
} [/code]
E a lista de adjacência seria um vetor de listas ligadas:
[code]public class ListaAdjacencia{
public static void main(String args[]){
//crio o vetor com 11 posicoes porque vou desprezar a posicao 0
ListaLigada[] listaAdjacencia = new ListaLigada[11];
//inicializo as listas ligadas
for(int i=1;i<=10;i++){
listaAdjacencia[i] = new ListaLigada();
}
//adiciona elementos na lista ligada da primeira posicao do vetor
listaAdjacencia[1].addFinal(2);
listaAdjacencia[1].addFinal(5);
//adiciona elementos na lista ligada da segunda posicao do vetor
listaAdjacencia[2].addFinal(1);
listaAdjacencia[2].addFinal(3);
listaAdjacencia[2].addFinal(5);
System.out.println("Lista encadeada no primeiro elemento do vetor:");
listaAdjacencia[1].listar();
System.out.println("Lista encadeada no segundo elemento do vetor:");
listaAdjacencia[2].listar();
}
}[/code]
marinagtto,
A implementação acima é bem básica.
Você pode obter implementações mais completas de algoritmos de grafo em Java no site abaixo:
http://www2.dcc.ufmg.br/livros/algoritmos-java/implementacoes-07.php
O item 7.3 do site implementa a lista de adjacência.
Muito obrigada al.barbosa, era exatamente isso que eu queria saber, me ajudou MUITO! 