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 …

Lista adjacente

Rodrigo_Sasaki 24 de mai. de 2012

você quer fazer uma matriz?

marinagtto 24 de mai. de 2012

quero fazer uma lista

al.barbosa 24 de mai. de 2012

marinagtto,

Entendi que você quer fazer uma lista de adjacência conforme descrito na wikipedia:

[url]http://pt.wikipedia.org/wiki/Lista_de_adjac%C3%AAncia[/url]

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.

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;   
                }   
  
        }   
}

E a lista de adjacência seria um vetor de listas ligadas:

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

al.barbosa 25 de mai. de 2012

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.

marinagtto 25 de mai. de 2012

Muito obrigada al.barbosa, era exatamente isso que eu queria saber, me ajudou MUITO!

5 Respostas

Topicos relacionados