Questão 5 - Kosaraju-Sharir's algorithm

Kosaraju-Sharir's algorithm is designed to find all Strongly Connected Components (SCCs) in a directed graph. It uses two main depth-first searches (DFS) to accomplish this. Which of the following steps correctly describe the main phases of the algorithm?

 

A - Perform a DFS on the graph to compute the finishing times of each vertex. Then, reverse the graph and perform another DFS based on decreasing finishing times.

B - Perform a BFS (Breadth-First Search) on the graph, followed by sorting the nodes based on their distances from the start vertex. Then, reverse the graph and repeat the BFS.

C - Reverse the graph, perform a DFS, and then compute a topological sort of the graph to find SCCs.

D - Use Dijkstra's algorithm to find the shortest path to each vertex, then reverse the graph and repeat the process.

E - None of above


Comentários

Postar um comentário

Postagens mais visitadas deste blog

Questão 1

  Consider the Depth-First Search (DFS) algorithm applied to a directed graph. Determine whether the following statements are true or false: 1-       1- In the DFS algorithm, if a vertex is visited, it will never be revisited. Therefore, by the end of the algorithm's execution, all vertices in the graph will have been visited once, assuming the graph is connected. 2-      2- When a vertex u is explored in DFS, its neighbors are explored in an order that depends on the graph structure. If a vertex v is a neighbor of u and has not been visited yet, it will be visited immediately after u.   3-      3- In DFS, the order in which vertices are visited can be used to construct a cycle and detect if a graph contains cycles. Mark which alternatives are correct: a- 1 and 2 b- 2 and 3 c- 3 d- 1 and 3 e- None of the above
Leia mais

Question 6 - Traveling Salesman

 Consider a traveling salesman who needs to visit 5 cities: A, B, C, D, and E. The distances (in kilometers) between the cities are as follows: A to B: 10 km A to C: 15 km A to D: 20 km A to E: 25 km B to C: 35 km B to D: 30 km B to E: 20 km C to D: 15 km C to E: 30 km D to E: 10 km What is the shortest possible route that the salesman can take, visiting each city exactly once and returning to the starting city? A) 70 km B) 85 km C) 90 km D) 100 km E)  None of above
Leia mais

Question 3 - Scale-free networks

  According to the book Network science by Albert-Lászlo Barabási,   the scale-free network property refers to:   A - A network in which all nodes have the same number of connections (degree). B - A network where the degree of all nodes follows a normal distribution. C - A network where most nodes have few connections, while a few highly connected nodes (hubs) have many connections. D - A network in which the number of connections between nodes grows exponentially over time E – None of above Original idea by: Vanessa Alves
Leia mais