# Question on Graph Theory(Tree)

Page 1 of 1

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

### #1 Asus93

• New D.I.C Head

Reputation: 0
• Posts: 27
• 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

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)

Is This A Good Question/Topic? 0

## Replies To: Question on Graph Theory(Tree)

### #2 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11948
• Posts: 44,715
• 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

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.

### #3 Asus93

• New D.I.C Head

Reputation: 0
• Posts: 27
• 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!