Graph Traversals Flashcards
1
Q
Two types
A
- DFS (depth-first search)
- BFS (breadth-first search)
2
Q
Properties of DFS
A
1: visits all the vertices and edges in the connected component of v
2: the discovery edges from a spanning tree of the connected component of v
3
Q
DFS
A
- discovery edges: paths taken
- back edge: w is an ancestor of v
4
Q
BFS
A
- discovery edge: path taken
- cross edge: w is in the same level as v or in the next level
5
Q
Directed DFS and BFS
A
- discovery arc: arcs leading to unvisited nodes in the traversal
- back arc: goes from a node to one of its ancestors
- forward arc: a non-spanning arc that goes from a node to a proper descendant
- cross arc: arcs that go from one node to another that is neither an ancestor nor a descendant
6
Q
String connectivity
A
Each vertex can reach all other vertices
7
Q
Reach ability
A
Vertices reachable from v via directed paths
8
Q
String connected components (SCC)
A
-is a maximal set of nodes in which there is a path from any node in the set to any other node in the set
9
Q
Equivalence classes
A
Such that v and w are equivalent iff there is a path from v to w and a path from w to v
