GrafoComListaDeAdjacencias.java

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class GrafoComListaDeAdjacencias implements Grafo {

	private List<Vertice> vertices = new ArrayList<>();
	private List<VerticeInterno> verticesInternos = new ArrayList<>();

	public GrafoComListaDeAdjacencias(String... nomesVertices) {
		for (String nomeVertice : nomesVertices) {
			this.addVertice(nomeVertice);
		}
	}
	public void buscaPorProfundidadeTotal() {
		boolean[] visitados = new boolean[vertices.size()];

		VerticeInterno naoVisitado = encontrarNaoVisitado(visitados);
		
		do {
			buscaP(naoVisitado, visitados);
		} while ( (naoVisitado = encontrarNaoVisitado(visitados) ) != null);
	}
	
	protected VerticeInterno encontrarNaoVisitado(boolean[] visitados) {
		for (int i = 0; i < visitados.length; i++) {
			boolean visitado = visitados[i];
			if (!visitado) {
				return verticesInternos.get(i);
			}
		}
		return null;
	}
	
	public void buscaPorProfundidade() {
		buscaPorProfundidade(vertices.get(0));
	}
	

	public void buscaPorProfundidade(Vertice vertice) {
		boolean[] visitados = new boolean[vertices.size()];
		buscaP(getVerticeInterno(vertice), visitados);
	}

	private void buscaP(VerticeInterno vertice, boolean[] visitados) {
		int posicao = verticesInternos.indexOf(vertice);
		
		if (visitados[posicao]) {
			return;
			
		} else {
			visitados[posicao] = true;
			System.out.println(vertice.getVertice().getNome());
			for (Aresta aresta : vertice.getArestas()) {
				
				buscaP(getVerticeInterno(aresta.getDestino()), visitados);		
			}
		}	
	}

	@Override
	public Vertice addVertice(String nome) {
		Vertice vertice = new Vertice();
		vertice.setNome(nome);
		vertices.add(vertice);
		
		VerticeInterno verticeInterno = new VerticeInterno();
		verticeInterno.setVertice(vertice);
		verticesInternos.add(verticeInterno);
		
		return vertice;
	}
	
	public Vertice getVertice(String nome) {
		for (Vertice vertice: vertices) {
			if (vertice.getNome().equals(nome)) {
				return vertice;
			}
		}
		
		return null;
	}
	
	private VerticeInterno getVerticeInterno(Vertice v) {
		for (VerticeInterno verticeInterno : verticesInternos) {
			if (verticeInterno.getVertice().equals(v)) {
				return verticeInterno;
			}
		}
		
		throw new RuntimeException("Vertice interno não encontrado");
	}

	@Override
	public void addAresta(Vertice v1, Vertice v2) {
		Aresta ida = new Aresta();
		ida.setOrigem(v1);
		ida.setDestino(v2);
		VerticeInterno verticeInternoV1 = getVerticeInterno(v1);
		verticeInternoV1.getArestas().add(ida);

		Aresta volta = new Aresta();
		volta.setOrigem(v2);
		volta.setDestino(v1);
		VerticeInterno verticeInternoV2 = getVerticeInterno(v2);
		verticeInternoV2.getArestas().add(volta);

	}

	@Override
	public List<Vertice> getVertices() {
		return vertices;
	}

	@Override
	public boolean conecta(Vertice v1, Vertice v2) {
		VerticeInterno verticeInternoV1 = getVerticeInterno(v1);
		
		for (Aresta aresta : verticeInternoV1.getArestas()) {
			if (aresta.getDestino().equals(v2)) {
				return true;
			}
		}
		
		return false;
	}
	
	public void buscaPorLargura(Vertice inicial) {
		boolean[] visitados = new boolean[vertices.size()];
		Queue<VerticeInterno> aVisitar = new LinkedList<>();
		
		VerticeInterno interno = getVerticeInterno(inicial);
		int posicaoInicial = verticesInternos.indexOf(interno);
		visitados[posicaoInicial] = true;
		
		aVisitar.offer(interno);
		
		while (!aVisitar.isEmpty()) {
			interno = aVisitar.remove();

			System.out.println(interno.getVertice().getNome());
			visitarArestas(visitados, aVisitar, interno);
		}
	}
	
	protected void visitarArestas(boolean[] visitados, Queue<VerticeInterno> aVisitar, VerticeInterno interno) {
		for (Aresta aresta : interno.getArestas()) {
			Vertice destino = aresta.getDestino();
			tentarEnfileirar(visitados, aVisitar, destino);
		}
	}
	
	protected void tentarEnfileirar(boolean[] visitados, Queue<VerticeInterno> aVisitar, Vertice destino) {
		VerticeInterno verticeInterno = getVerticeInterno(destino);
		
		if (!visitados[verticesInternos.indexOf(verticeInterno)]) {
			visitados[verticesInternos.indexOf(verticeInterno)] = true;
			aVisitar.offer(verticeInterno);
		}
	}

}

class VerticeInterno {

	private Vertice vertice;
	private List<Aresta> arestas = new ArrayList<>();

	public Vertice getVertice() {
		return vertice;
	}

	public void setVertice(Vertice vertice) {
		this.vertice = vertice;
	}

	public List<Aresta> getArestas() {
		return arestas;
	}

}

GrafoComListaDeAdjacenciasTest.java

import static org.junit.Assert.*;

import org.junit.Test;

public class GrafoComListaDeAdjacenciasTest {

	@Test
	public void testLargura() {
		GrafoComListaDeAdjacencias grafo = 
				new GrafoComListaDeAdjacencias("JP", "MA", "AL", "GU", "CG",
						"QU", "AC", "PA", "MO", "PI", "SO", "CJ");
		
		Vertice jp = grafo.getVertice("JP");
		Vertice ma = grafo.getVertice("MA");
		Vertice al = grafo.getVertice("AL");
		Vertice gu = grafo.getVertice("GU");
		Vertice cg = grafo.getVertice("CG");
		Vertice qu = grafo.getVertice("QU");
		Vertice ac = grafo.getVertice("AC");
		Vertice pa = grafo.getVertice("PA");
		Vertice mo = grafo.getVertice("MO");
		Vertice pi = grafo.getVertice("PI");
		Vertice so = grafo.getVertice("SO");
		Vertice cj = grafo.getVertice("CJ");

		grafo.addAresta(jp, ma);
		grafo.addAresta(jp, gu);
		grafo.addAresta(jp, cg);
		grafo.addAresta(jp, al);
		grafo.addAresta(cg, gu);
		grafo.addAresta(cg, pi);
		grafo.addAresta(cg, pa);
		grafo.addAresta(cg, mo);
		grafo.addAresta(cg, qu);
		grafo.addAresta(pa, so);
		grafo.addAresta(qu, ac);
		grafo.addAresta(so, cj);

		//JP MA GU CG AL PI PA MO QU SO AC CJ
		grafo.buscaPorLargura(jp);
		
	}
	
	
	
	
	

}