import java.util.LinkedList;
import java.util.Queue;
/**
*
* @author David
*/
public class Graph {
private int V;
private LinkedList<Integer> adj[];
Graph( int v ) {
V = v;
adj = new LinkedList[v];
for ( int i = 0; i < v; ++i ) {
adj[i] = new LinkedList();
}
}
void addEdge( int v, int w ) {
adj[v].add( w );
adj[w].add( v );
}
void BFS( int s ) {
boolean visited[] = new boolean[V];
Queue<Integer> queue = new LinkedList<>();
visited[s] = true;
queue.add( s );
while ( !queue.isEmpty() ) {
s = queue.poll();
System.out.println( s + " " );
for ( int n : adj[s] ) {
if ( !visited[n] ) {
visited[n] = true;
queue.add( n );
}
}
}
}
public static void main( String args[] ) {
Graph g = new Graph( 4 );
g.addEdge( 0, 1 );
g.addEdge( 0, 2 );
g.addEdge( 1, 2 );
g.addEdge( 2, 3 );
System.out.println( "A seguir está a primeira travessia em largura " + "(starting from vertex 2)" );
g.BFS( 2 );
}
}
Ao adicionar uma aresta em um grafo não dirigido, vc precisa fazer a ida e a volta. Veja o que mudou no método addEdge. Se já existe ida e volta, a chamada g.addEdge(2, 0); insere um “anomalia” no seu grafo, chamada de aresta paralela. Ela pode existir, não há problema, só vai fazer seu algoritmo demorar um pouco mais. Outra anomalia do seu exemplo, que tbm pode existir é o laço/loop criado na chamada g.addEdge(3, 3); que não terá efeito algum sobre a busca em largura, visto que o vértice atual será marcado como visitado assim que for alcançado. Na ordem em que estão feitas as inserções das arestas no meu exemplo, removendo as duas chamadas acima, você terá o array adj populado da seguinte forma:
Os valores entre chaves representam as listas usadas. Lembre-se que as inserções são feitas na cauda/rabo/fim da lista e são feitas nas duas direções.
Você inicia a busca pelo vértice 2, então terá algo assim durante a execução:
// início
visited = F | F | F | F (F = false, T = true)
0 1 2 3
queue = {}
// inserção da fonte na fila e marcação de visitado
visited = F | F | T | F
0 1 2 3
queue = { 2 }
// a fila está vazia? não!
s = 2
queue = {}
adjacentes de 2:
3: visitado? não!
visited[3] = true; => visited = F | F | T | T
queue = { 3 } 0 1 2 3
1: visitado? não!
visited[1] = true; => visited = F | T | T | T
queue = { 1, 3 } 0 1 2 3
0: visitado? não!
visited[0] = true; => visited = T | T | T | T
queue = { 0, 1, 3 } 0 1 2 3
// perceba que no seu exemplo, todos os vértices
// já estão visitados e a árvore de busca em largura
// gerada já está pronta (seu exemplo não a codifica,
// se quiser eu complemento para vc.
// a ideia da busca em largura é obter essa árvore e
// os custos associados a quantidade de "pulos" que se
// da de um vértice a outro, sendo algo parecido com um
// algoritmo de menor caminho, mas sem pesos nas arestas
// continuando...
// a fila está vazia? não!
s = 3
queue = { 0, 1 }
adjacentes de 3:
2: visitado? sim!
// a fila está vazia? não!
s = 1
queue = { 0 }
adjacentes de 1:
2: visitado? sim!
0: visitado? sim!
// a fila está vazia? não!
s = 0
queue = {}
adjacentes de 0:
2: visitado? sim!
1: visitado? sim!
// a fila está vazia? sim!
Sim, só que não é armazenada a árvore e as distâncias. Ele mostra na saída os vértices que estão sendo processados no momento que saem da fila. O ideal seria ter algo mais robusto do ponto de vista de utilidade. Veja o terceiro link que te passei. O array edgeTo armazena o caminho da árvore e o array distTo armazena as distâncias da fonte até o vértice em questão. Acho que foi vc que perguntou sobre busca em profundidade há alguns dias atrás não foi? A ideia é a mesma.
Meu questionamento não foi o int no construtor, que determina a quantidade de vértices, mas o motivo de ele usar int para representar os vértices sendo que no desenho eles são representados por letras.
Se ele quisesse representar o grafo do desenho, sua classe Graph seria adaptada para funcionar com char ou String ao invés de int, poderia até fazer algo mais elaborado com uma classe Vertex para servir de container genérico.
Mas enfim, a ideia seria representar o grafo da imagem dessa forma:
Um dos motivos, o principal na verdade, é o acesso direto ao índice do array que armazena as listas de adjacências, pq a ideia é ter uma implementação “ótima” de um grafo. É claro, vc poderia fazer um mapeamento char → int, mas se há a necessidade de armazenar rótulos para os vértices a abordagem normal é usar uma tabela de símbolos para associar o vértice (inteiro) com o rótulo.
