[Asus93]

Find the spanning tree from the following graph by using
a.Depth First Search
b.Breadth-First Search

Assume A is the root and the vertices are ordered as A,B,C,D,E

I have problems on both options after trying it.

For DFS, here's my workings:

1. A , Edge()
2. AB , Edge( AB )
3. ABD , Edge( AB,BD )
4. ABDE , Edge(AB,BD, DE)
5. ABDEF , Edge(AB, BD, DE, EF)

I stopped here because I'm not sure whether vertex G is included or not? since adjacent of D in ordered pair will go to vertex E instead of G

For BFS,here's my workings:

1. A, Edge()
2. AB , Edge(AB)
3. ABC, Edge(AB,AC)
4. ABCF, Edge(AB,AC,AF)
5. BCF, Edge(AB,AC,AF)

now,the adjacent of B will be D, so should I write BCFD or BCDF? since the question would request me to write in ordered pair.

Can someone guides me? I appreciate your time!
Thanks!

Attached image(s)

• 

[macosxnerd101]

The algorithm for a DFT is as follows:

dfs(root)
  foreach unvisited child of root
     mark child as visited
     dfs(child)

So for a DF Spanning Tree starting at A, that would visit the vertices in the order ABDECFG (visiting the children of E in alphabetical order, though the order of CFG can be changed).

Breadth-first traversal works similarly, but evaluates all the children of root before recursing.

bfs(root)
   unvisited_children = array()
   foreach unvisited child of root
       mark child as visited
       unvisited_children.add(child)

   foreach child in unvisited_children
       bfs(child)

For the BF Spanning Tree, you would denote that the vertices were visited initially in the order ABCF. The next vertex that is visited is D from the adjacency to B. From there, D is evaluated recursively.

Hope this helps some.

[Asus93]

Hi macosxnerd,
Great thanks for your guides!That really helps!