Número:
Enunciado:
Tomando em conta a
seguinte versão do algoritmo de busca em largura:
BFS(G,s)
1
for
each vertex u∈G.V\{s}
2
u.color =
WHITE
3
u.d =
∞
4
u.π = NIL
5
s.color=GRAY
6
s.d=0
7
s.π=NIL
8
Q=∅
9
ENQUEUE(Q,
s)
10
while
Q̸=∅
11
u = DEQUEUE(Q)
12
for
each v
∈ G.Adj[u]
13
if
v.color
==
WHITE
14
v.color =
GRAY
15
v.d =
u.d
+ 1
16
v.π = u
17
ENQUEUE(Q,
v)
18 u.color =
BLACK
Faça a execução do algoritmo
BFS com o grafo
representado pela seguinte matriz de adjacência e iniciando a partir do vértice "a":
|
|
a
|
b
|
c
|
d
|
e
|
f
|
|
a
|
0
|
1
|
0
|
1
|
1
|
0
|
|
b
|
1
|
0
|
1
|
0
|
0
|
0
|
|
c
|
0
|
1
|
0
|
1
|
0
|
0
|
|
d
|
1
|
0
|
1
|
0
|
1
|
1
|
|
e
|
1
|
0
|
0
|
1
|
0
|
0
|
|
f
|
0
|
0
|
0
|
1
|
0
|
0
|
Indique quais são os predecessores π
de cada vértice.
a)
a.π=NIL, b.π=a, c.π=d, d.π=f, e.π=a, f.π=d
b)
a.π=NIL, b.π=c, c.π=b, d.π=f, e.π=a, f.π=a
c)
a.π=NIL, b.π=a, c.π=d, d.π=a, e.π=a, f.π=a
d)
a.π=NIL, b.π=a, c.π=b, d.π=a, e.π=a, f.π=d
e)
NDA
Ideia original de: Sheila Katherine Venero Ferro
Nenhum comentário:
Postar um comentário