CSE 2321 Final
Breadth-First Search (BFS) - ANS-Search all directions evenly (i.e., from i, visit all of i's
neighbors, then all of their neighbors, etc.)
- Can find the distance between two vertices
- Can find the distance of all vertices from the source vertex
- Can tell us the number of components of an undirect graph
- Can tell us when an undirect graph is bipartite
Depth First Search - ANS-A search in which children of a node are considered
(recursively) before siblings are considered.
Vertices are white when nothing other than initialization happened to them. Turn gray
when being worked on. Black when algorithm is finished with them.
u.pi is predecessor
u.d is time vertex was discovered
u.f is time algorithm finished with the vertex
Tree Edge - ANS-When the BFS algorithm first encounters the edge, it is pointing from
a gray vertex to a white one
Back Edges - ANS-From a gray vertex to a gray vertex when it encounters is
Forward Edges - ANS-From a gray vertex to a black vertex. If the discovery times for
the gray vertex are less than the black.
Cross Edges - ANS-From gray to black where the tree edges don't make a path. If the
discovery time for the black vertex is less than the gray.
Bipartite Graph - ANS-a graph that can be divided into two sets of vertices where there
are no edges between vertices in the same set
No edges between vertices from the same set.
Breadth-First Search (BFS) - ANS-Search all directions evenly (i.e., from i, visit all of i's
neighbors, then all of their neighbors, etc.)
- Can find the distance between two vertices
- Can find the distance of all vertices from the source vertex
- Can tell us the number of components of an undirect graph
- Can tell us when an undirect graph is bipartite
Depth First Search - ANS-A search in which children of a node are considered
(recursively) before siblings are considered.
Vertices are white when nothing other than initialization happened to them. Turn gray
when being worked on. Black when algorithm is finished with them.
u.pi is predecessor
u.d is time vertex was discovered
u.f is time algorithm finished with the vertex
Tree Edge - ANS-When the BFS algorithm first encounters the edge, it is pointing from
a gray vertex to a white one
Back Edges - ANS-From a gray vertex to a gray vertex when it encounters is
Forward Edges - ANS-From a gray vertex to a black vertex. If the discovery times for
the gray vertex are less than the black.
Cross Edges - ANS-From gray to black where the tree edges don't make a path. If the
discovery time for the black vertex is less than the gray.
Bipartite Graph - ANS-a graph that can be divided into two sets of vertices where there
are no edges between vertices in the same set
No edges between vertices from the same set.
