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 
Review: Breadth-First Search 
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 
Review: Breadth-First Search 
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; 
   for each v ? u->Adj[] 
   { 
      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 
Review: Breadth-First Search 
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; 
   for each v ? u->Adj[] 
   { 
      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 
Review: Breadth-First Search 
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; 
   for each v ? u->Adj[] 
   { 
      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 
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

Content Category

Related Searches

past year papers

,

Extra Questions

,

Exam

,

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

,

Important questions

,

MCQs

,

Objective type Questions

,

study material

,

Sample Paper

,

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

,

ppt

,

practice quizzes

,

video lectures

,

Previous Year Questions with Solutions

,

Semester Notes

,

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

,

Free

,

Viva Questions

,

Summary

,

shortcuts and tricks

,

mock tests for examination

,

pdf

;