CS 225 Lecture 40: Graph Traversals
Document Summary
Visited vertex a, give it when visited (0), and enqueue the vertex, then we dequeue the vertex, and do a for loop across all of the vertex"s adjacent vertices. C is first in the loop, visit it, mark it with time, and enqueue into the vertex. Go to the next one, b and do the same exact thing as c, then we go to d and do the same thing again. Each time we visit a new node, we mark the edge between the two as discovered. Then we"re done with a, next we dequeue the next vertex, c. C discovers e. we can easily check whether the edge is done. An easy way to check is if we look at whether the vertex comes before the current vertex in the list, or if we use numbers instead of letters. Check if vertex is greater then the one we are checking.