Directed Graphs quiz
How many different digraphs are there on V vertices? Allow self-loops but do now allow self-edges.
V
2
V
2
(V
2
)
2
(2
V
)
Submit
Suppose that a digraph G is represented using the adjacency-lists representation. What is the order of growth of the running time to find all vertices that point to a given vertex v?
indegree(v)
outdegree(v)
V
V + E
Submit
Suppose that during an execution of depth-first search in a digraph G,
dfs(v)
is called after
dfs(w)
is called, but before
dfs(w)
returns. Which of the following must be true of the graph G?
There exists a directed path from v to w.
There exists a directed path from w to v.
There does not exist a directed path from v to w.
There exists a directed cycle containing both v and w.
Submit
How many strong components does a DAG on V vertices and E edges have?
0
1
V
E
Submit