Generally, what is the difference between a breadth first search (BFS) and a depth first search (DFS)?
A breadth first search finds all nodes within one hop of the current node to place at the same level, while a depth first search always attempts to search deeper into the graph whenever possible.
What does the distance between nodes (number of edges) in a BFS represent?
The shortest distance between two nodes.
(T/F) A depth first search only works on a directed graph.
False. A DFS can be performed on a directed or undirected graph.
(T/F) A starting node must be input for DFS, in addition to the graph's sets of vertices and edges.
False. DFS will examine every vertex (node) in the graph, starting new trees if needed.
What does the phrase "forest of trees" refer to?
The nature of DFS often results in multiple trees - or a forest of trees.
When a DFS is performed, what 2 pieces of information are stored on each node (vertex) that are not when a BFS is performed?
The vertex's discovery time and the vertex's finishing time. These are integer timestamps that indicate the relative order of the traversal of the graph.
(T/F) It is possible to determine if a node x is the descendant or ancestor (or neither) of node y based on the information stored in a DFS.
True. The parenthesis theorem states that if the interval of a node u (discovery time, finishing time) lies entirely within the interval of a node v, then u is a descendant of v.
(T/F) A depth first search will methodically explore every edge in a graph.
True. It will start over from different vertices if necessary.
What are two major differences in how BFS and DFS execute?
BFS enqueues a node when it discovers it, while DFS explores it immediately.
BFS starts from one node, but DFS may "start" from several nodes. This means BFS creates one tree, while DFS may create a forest of trees.
What are the three colors vertices can have in DFS and what do they indicate?
WHITE - undiscovered
GRAY - discovered, but not finished (not done exploring from it)
BLACK - finished (all nodes reachable from it have been reached - are GRAY)
What is the range of possible discovery times and finishing times?
1 - 2*V (Start at 1, each vertex has 2 times - discovery and finishing)
For any vertex v, what can be said about its discovery time and finishing time?
v.discovery_time < v.finishing_time
or, 1 <= v.discovery <= v.finishing <= 2*V
Look at the pseudocode for Depth First Search (recursive version).
What are the four types of edges in a DFS?
1. tree (if vertex v is discovered for the first time when an edge is traversed, that edge is a tree edge)
2. back edge - (if vertex v has already been discovered and v is a ancestor of u, that edge is a back edge)
3. forward edge - (if vertex v has already been discovered and v is a descendant of u, that edge is a forward edge)
4. cross edge - (if vertex v has already been discovered, but v is neither an ancestor nor a descendant of u, that edge is a cross edge)
When a vertex is discovered, what can the color of that node tell us about the type of edge we are exploring?
WHITE - tree edge
GRAY - back edge
BLACK - forward or cross edge
Cross edges can go between vertices in _____________ or ____________.
the same DFS, different DFSs
Which two types of edges never occur in a depth first search of an undirected graph? Why?
forward, cross.
There cannot be forward edges because it is an undirected graph (forward and back are not distinguishable).
There cannot be cross edges in an undirected graph because cross edges occur on edges where a black (finished) node is reached from a node that is neither its ancestor or descendant.
Show how DFS works on the slide showing a directed graph.
What type of graph is topological sort performed on?
A dag.
What is a dag?
A directed acyclic graph.
Generally describe topological sort.
A topological sort of a dag is a linear ordering of all of its vertices such that if G contains an edge (u,v) then u appears before v in the ordering. Remember, the graph is directed!
What is important to note about the ordering of vertices (along a horizontal line) in a topological sort?
All directed edges go from left to right.
What are a few uses of dags?
A dag can be used to indicate causality (which risk factors cause a disease).
A dag can be used to handle scheduling (college courses, airline schedules).
Dags can also be used to model dependencies (e.g., which steps must precede other steps in a process).
<\answer>
Look at the example dag and topological slides (batman).
Look at the pseudocode for topological sort.
Generally speaking, how does one perform a topological sort?
Given a graph G, do a depth first search (DFS) for the graph to compute the finishing time for the nodes.
As each node finishes, insert it onto the front of a linked list. (This is really a stack - push onto the top (LIFO)).
Return the linked list of vertices.
What is the time complexity of Topological sort?
theta(V+E)
Can DFS be used to detect a dag?
Yes - a directed graph is acyclic iff a depth-first search (DFS) of G yields no back edges.
