Courses

# SPANNING TREE ALGORITHM Computer Science Engineering (CSE) Notes | EduRev

## Computer Science Engineering (CSE) : SPANNING TREE ALGORITHM Computer Science Engineering (CSE) Notes | EduRev

``` Page 1

David Luebke             1                 4/12/2014
CS 332: Algorithms
Topological Sort
Minimum Spanning Trees
Page 2

David Luebke             1                 4/12/2014
CS 332: Algorithms
Topological Sort
Minimum Spanning Trees
David Luebke             2                 4/12/2014
BFS(G, s) {
initialize vertices;
Q = {s};  // Q is a queue (duh); initialize to s
while (Q not empty) {
u = RemoveTop(Q);
for each v ? u->adj {
if (v->color == WHITE)
v->color = GREY;
v->d = u->d + 1;
v->p = u;
Enqueue(Q, v);
}
u->color = BLACK;
}
}
v->p represents parent in tree
v->d represents depth in tree
Page 3

David Luebke             1                 4/12/2014
CS 332: Algorithms
Topological Sort
Minimum Spanning Trees
David Luebke             2                 4/12/2014
BFS(G, s) {
initialize vertices;
Q = {s};  // Q is a queue (duh); initialize to s
while (Q not empty) {
u = RemoveTop(Q);
for each v ? u->adj {
if (v->color == WHITE)
v->color = GREY;
v->d = u->d + 1;
v->p = u;
Enqueue(Q, v);
}
u->color = BLACK;
}
}
v->p represents parent in tree
v->d represents depth in tree
David Luebke             3                 4/12/2014
Review: DFS Code
DFS(G)
{
for each vertex u ? G->V
{
u->color = WHITE;
}
time = 0;
for each vertex u ? G->V
{
if (u->color == WHITE)
DFS_Visit(u);
}
}
DFS_Visit(u)
{
u->color = YELLOW;
time = time+1;
u->d = time;
{
if (v->color == WHITE)
DFS_Visit(v);
}
u->color = BLACK;
time = time+1;
u->f = time;
}
Page 4

David Luebke             1                 4/12/2014
CS 332: Algorithms
Topological Sort
Minimum Spanning Trees
David Luebke             2                 4/12/2014
BFS(G, s) {
initialize vertices;
Q = {s};  // Q is a queue (duh); initialize to s
while (Q not empty) {
u = RemoveTop(Q);
for each v ? u->adj {
if (v->color == WHITE)
v->color = GREY;
v->d = u->d + 1;
v->p = u;
Enqueue(Q, v);
}
u->color = BLACK;
}
}
v->p represents parent in tree
v->d represents depth in tree
David Luebke             3                 4/12/2014
Review: DFS Code
DFS(G)
{
for each vertex u ? G->V
{
u->color = WHITE;
}
time = 0;
for each vertex u ? G->V
{
if (u->color == WHITE)
DFS_Visit(u);
}
}
DFS_Visit(u)
{
u->color = YELLOW;
time = time+1;
u->d = time;
{
if (v->color == WHITE)
DFS_Visit(v);
}
u->color = BLACK;
time = time+1;
u->f = time;
}
David Luebke             4                 4/12/2014
Review: DFS Example
source
vertex
Page 5

David Luebke             1                 4/12/2014
CS 332: Algorithms
Topological Sort
Minimum Spanning Trees
David Luebke             2                 4/12/2014
BFS(G, s) {
initialize vertices;
Q = {s};  // Q is a queue (duh); initialize to s
while (Q not empty) {
u = RemoveTop(Q);
for each v ? u->adj {
if (v->color == WHITE)
v->color = GREY;
v->d = u->d + 1;
v->p = u;
Enqueue(Q, v);
}
u->color = BLACK;
}
}
v->p represents parent in tree
v->d represents depth in tree
David Luebke             3                 4/12/2014
Review: DFS Code
DFS(G)
{
for each vertex u ? G->V
{
u->color = WHITE;
}
time = 0;
for each vertex u ? G->V
{
if (u->color == WHITE)
DFS_Visit(u);
}
}
DFS_Visit(u)
{
u->color = YELLOW;
time = time+1;
u->d = time;
{
if (v->color == WHITE)
DFS_Visit(v);
}
u->color = BLACK;
time = time+1;
u->f = time;
}
David Luebke             4                 4/12/2014
Review: DFS Example
source
vertex
David Luebke             5                 4/12/2014
Review: DFS Example
1 |     |     |
|    |   |
|     |
source
vertex
d      f
```
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

;