Use breadth-first search to produce a spanning tree for the graph below starting

Question

Use breadth-first search to produce a spanning tree for the graph below starting from vertex a. Draw the spanning tree or write the list of edges.

Explanation / Answer

First vertex = a List = {a[nil]} BFS :- POP x from the list and put {all UNVISITED children of x along with x} in the list When POP add the edge from parent of x to x in the path now POP from the list and put {b[a],g[a]} in the list (queue) List = {b[a],g[a]} Path = a POP b[a] and push c[b] List = {g[a],c[b]} Path = {a -> b} POP g[a] and push h[g],l[g] List = {c[b],h[g],l[g]} Path = {a -> b, a->h} Similarly POP c[b] and h[g] , l[g] List = {i[h],m[h]} Path = {a -> b, a->h , b -> c , g-> h, g -> l} Similarly POP i[h],m[h] List = {d[i],e[i],j[i],n[i]} Path = {a -> b, a->h , b -> c , g-> h, g -> l,h->m, h->i } POP d[i],e[i],j[i],n[i] List = {f[e],k[j]} Path = {a ->b, a->h , b ->c , g->h, g ->l, h->m, h->i, i->d, i->e,i->j, i->n } Finally POP f[e],k[j] Final PATH = {a ->b, a->h , b ->c , g->h, g ->l, h->m, h->i, i->d, i->e,i->j, i->n, e->f, j->k }

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.