2 Replies - 1232 Views - Last Post: 04 August 2013 - 09:32 AM

#1 Asus93  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 26
  • Joined: 22-July 13

Question on Graph Theory(Tree)

Posted 03 August 2013 - 10:34 PM

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)

  • Attached Image


Is This A Good Question/Topic? 0
  • +

Replies To: Question on Graph Theory(Tree)

#2 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10803
  • View blog
  • Posts: 40,264
  • Joined: 27-December 08

Re: Question on Graph Theory(Tree)

Posted 03 August 2013 - 10:52 PM

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.
Was This Post Helpful? 1
  • +
  • -

#3 Asus93  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 26
  • Joined: 22-July 13

Re: Question on Graph Theory(Tree)

Posted 04 August 2013 - 09:32 AM

Hi macosxnerd,
Great thanks for your guides!That really helps!
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1