(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)
;
(4)
;
(2)
;
(5)
.
(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.
(0)
(3)
(1)
(4)
(2)
(5)
(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.
Passo 1
O enunciado dá um grafo não direcionado com os vértices
e as seguintes listas de adjacência:
– :
– :
– :
– :
– :
– :
–
–
–
–
–
–
Precisamos:
(a) desenhar o grafo;
(b) a ordem de visita dos seis vértices em busca em profundidade (DFS) partindo de , respeitando a ordem dada em cada lista;
(c) a ordem de visita em busca em largura (BFS) partindo de , também respeitando a ordem dada.
(a) desenhar o grafo;
(b) a ordem de visita dos seis vértices em busca em profundidade (DFS) partindo de
(c) a ordem de visita em busca em largura (BFS) partindo de
Passo 2
Para desenhar o grafo, primeiro liste as arestas únicas (grafo não direcionado):
.
Uma forma de desenhar é posicionar os seis vértices em torno de um hexágono e ligar cada par acima. Por exemplo:
– Coloque e
vizinhos na base,
– e
no topo,
– à direita e
à esquerda,
de modo que todas as arestas listadas sejam traçadas entre os vértices correspondentes.
Uma forma de desenhar é posicionar os seis vértices em torno de um hexágono e ligar cada par acima. Por exemplo:
– Coloque
–
–
de modo que todas as arestas listadas sejam traçadas entre os vértices correspondentes.
Passo 3
Executando DFS a partir de
, marcamos como visitado e aprofundamos sempre no próximo vizinho não visitado, na ordem da lista:
- Visita
. Vizinhos de : . - Vai a
. Vizinhos de : . - Vai a
. Vizinhos de : . - Vai a
. Vizinhos de : . - Vai a
. Vizinhos de : . - Vai a
. Vizinhos de : .
Não há mais vértices não visitados.
Ordem DFS:
Passo 4
Executando BFS a partir de
, enfileiramos os vizinhos na ordem dada e depois processamos na ordem de saída da fila:
- Entra
. Fila= . Visita e enfileira vizinhos de : . - Processa
. Enfileira de : só (os outros já visitados). Fila= . - Processa
. Nenhum novo. Fila= . - Processa
. Nenhum novo. Fila= . - Processa
. Nenhum novo. Fila= . - Processa
. Nenhum novo. Fila vazia.
Ordem BFS:
Resposta
(a) O grafo possui as arestas
,
desenhadas conforme descrição acima.
(b) DFS a partir de :
(c) BFS a partir de :
desenhadas conforme descrição acima.
(b) DFS a partir de
(c) BFS a partir de