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 fRead More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!