# Graph Traversals Flashcards Preview

## Csc 225 > Graph Traversals > Flashcards

Flashcards in Graph Traversals Deck (9)
1
Q

Two types

A
• DFS (depth-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