jho

MO417 - Questão para a prova oral

Número: 

Enunciado: Dado o seguinte grafo dirigido A=(V,E)  :

  

Y os seguintes algoritmos:

DFS(G)                                                      

1 for each vertex u ∈ G.V                         

2       u.color = WHITE                            

3       u.π = NIL                                        

4 time = 0                                                 

5 for each vertex u ∈ G.V                          

6       if u.color == WHITE                       

7           DFS-VISIT(G,u)                        

                                                                                                                         
DFS-VISIT(G,u)  

1 time = time + 1
2 u.d = time
3 u.color = GRAY 
4 for each v ∈ G.Adj[u] 
5       if v.color = = WHITE 
6             v.π = u  
7             DFS-VISIT(G,v) 
8 u.color = BLACK 
9 time = time + 1 
10 u.f = time
  
Suponha que seu vetor de listas de listas de adjacência como seus lista de adjacência de cada vértice estam armazenados em orden alfabética. Assinale alternativa que contém o valor π correto de cada um dos vertices do grafo A, após da execução do algoritmo DFS(A): 

1.)a.π = f, b.π = a, c.π = d, d.π = b, e.π = NIL, f.π = b, g.π = NIL
2.)a.π = NIL, b.π = a, c.π = d, d.π = b, e.π = NIL, f.π = b, g.π = NIL
3.)a.π = NIL, b.π = a, c.π = b, d.π = d, e.π = NIL, f.π = b, g.π = NIL
4.)a.π = NIL, b.π = a, c.π = d, d.π = b, e.π = NIL, f.π = NIL, g.π =b
5.)NDA

Ideia original de: Jhon Anthony Campos Arteaga