(7 pontos) Considere um grafo nāo-direcionado (não-dirigido) com 6 vértices, os quais possuem as seguintes listas de adjacências:
(0) 3,1,5;
(3) 0,2,4;
(1) 4,5,0,2;
(4) 1,2,5,3;
(2) 4,3,1;
(5) 1,4,0.
(a) ( 3 pontos) Desenhe o grafo.
(b) ( 3 pontos) Partindo-se do vértice 1 , liste os seis vértices, na ordem em que os mesmos são visitados, considerando-se a busca em profundidade.
(c) (1 ponto) Partindo-se do vértice 1, liste os seis vértices, na ordem em que os mesmos são visitados, considerando-se a busca em largura.
Para os itens b e c acima, a ordem dada nas listas de adjacências deve ser respeitada.

Passo 1

O enunciado dá um grafo não direcionado com os vértices \{0,1,2,3,4,5\} e as seguintes listas de adjacência:
(0): 3,1,5
(1): 4,5,0,2
(2): 4,3,1
(3): 0,2,4
(4): 1,2,5,3
(5): 1,4,0
Precisamos:
(a) desenhar o grafo;
(b) a ordem de visita dos seis vértices em busca em profundidade (DFS) partindo de 1, respeitando a ordem dada em cada lista;
(c) a ordem de visita em busca em largura (BFS) partindo de 1, também respeitando a ordem dada.

Passo 2

Para desenhar o grafo, primeiro liste as arestas únicas (grafo não direcionado): (0,3),\,(0,1),\,(0,5),\,(1,4),\,(1,5),\,(1,2),\,(2,3),\,(2,4),\,(3,4),\,(4,5).
Uma forma de desenhar é posicionar os seis vértices em torno de um hexágono e ligar cada par acima. Por exemplo:
– Coloque 0 e 1 vizinhos na base,
2 e 3 no topo,
4 à direita e 5 à esquerda,
de modo que todas as arestas listadas sejam traçadas entre os vértices correspondentes.

Passo 3

Executando DFS a partir de 1, marcamos como visitado e aprofundamos sempre no próximo vizinho não visitado, na ordem da lista:
  1. Visita 1. Vizinhos de 1: 4,5,0,2.
  2. Vai a 4. Vizinhos de 4: 1\,(já),2,5,3á.
  3. Vai a 2. Vizinhos de 2: 4\,(já),3,1\,(já)áá.
  4. Vai a 3. Vizinhos de 3: 0,2\,(já),4\,(já)áá.
  5. Vai a 0. Vizinhos de 0: 3\,(já),1\,(já),5áá.
  6. Vai a 5. Vizinhos de 5: 1\,(já),4\,(já),0\,(já)ááá.
    Não há mais vértices não visitados.
Ordem DFS:
[\,1,\,4,\,2,\,3,\,0,\,5\,].

Passo 4

Executando BFS a partir de 1, enfileiramos os vizinhos na ordem dada e depois processamos na ordem de saída da fila:
  1. Entra 1. Fila= [1]. Visita e enfileira vizinhos de 1: [4,5,0,2].
  2. Processa 4. Enfileira de 4: só 3 (os outros já visitados). Fila= [5,0,2,3].
  3. Processa 5. Nenhum novo. Fila= [0,2,3].
  4. Processa 0. Nenhum novo. Fila= [2,3].
  5. Processa 2. Nenhum novo. Fila= [3].
  6. Processa 3. Nenhum novo. Fila vazia.
Ordem BFS:
[\,1,\,4,\,5,\,0,\,2,\,3\,].

Resposta

(a) O grafo possui as arestas (0,3),\,(0,1),\,(0,5),\,(1,4),\,(1,5),\,(1,2),\,(2,3),\,(2,4),\,(3,4),\,(4,5),
desenhadas conforme descrição acima.
(b) DFS a partir de 1: [1,4,2,3,0,5]
(c) BFS a partir de 1: [1,4,5,0,2,3]

Exercícios relacionados