Quiz question 03

How does the Kosaraju–Sharir algorithm identify Strongly Connected Components (SCC)?

a.) Performs a DFS on a graph G. Then, it orders the nodes by decreasing finishing times. The branches found by the DFS are considered strongly connected components.

b.) Applies only to cyclic graphs. If a cycle has more than three nodes, then it is considered a strongly connected component.

c.) Performs a DFS on a graph G. Then, it orders the nodes by decreasing finishing times. This order is used to perform a second DFS on the transposed graph G′ (where all edges are reversed). The trees formed during this DFS are considered strongly connected components.

d.) Identifies cycles in a graph G, where for any pair of nodes u and v, there is a path from u to v and from v to u.

e.) None of the above

Original idea by: Julia de Pietro Bigi

Comentários

Postar um comentário

Postagens mais visitadas deste blog

Quiz question 01

Imagem
Consider the following network: Which statements are TRUE or FALSE? 1. The degree distribution of this network would generate a graph with equal values of pk for k values.  2. If link (4-5) were to be removed, then the network would have 2 components. This makes the connection between nodes 4 and 5 to be called a bridge. 3. Considering node 4 as the zero node, the diameter of this network is dmax = 4. 4. The degrees of the two mostl connected nodes are equivalent to 2/3 and 1.  a.) T F F T b.) F F T T c.) T T F T  d.) F T T F  e) None of the above Original idea by: Julia de Pietro Bigi
Leia mais

Quiz question 02

What do BFS and DFS have in common? What about their differences?  a.) Common: They both use an adjacency list as input. Both of them can be used to calculate distances and classify edges. Differences: BFS doesn't restart the search when it reaches a target node or when a tree is finished like DFS does. BFS visits all nodes reachable from a given node, so not necessarily the entire tree will be visited. b.) Common: they both use an adjancency list and starting + ending times of node's visits as input.  Differences: BFS can be used to calculate distances and finding connected components. While DFS can be used to detect cycles and classify edges.  c.) Common: they both use an adjancency list as input.  Differences: BFS doesn't restart the search when it reaches a target node or when a tree is finished like DFS does. BFS visits all nodes reachable from a giving node, so not necessarily the entire tree will be visited.  d.) Common: they both need an adjancency list ...
Leia mais