Write an algorithm to determine if the directed graph is strongly connected or not

Solutions

Expert Solution

Answer) Checking if a graph is strongly connected using Kosaraju’s DFS based simple algorithm that does two DFS traversals of graph:

1) Initialize all vertices as they are not visited.

2) Do the DFS traversal of the graph starting from any arbitrary vertex v. If the DFS traversal does not visit all the vertices then return false.

3) Reverse all arcs (or find transpose).

4) Mark all vertices as not-visited in the reversed graph.

5) Do a DFS traversal of the reversed graph starting from same vertex v (Same as step 2). If the DFS traversal does not visit all the vertices then return false. Otherwise, return true.

The idea is that if every node can be reached from vertex v, and every node can reach v, then the graph is strongly connected. In step 2, we check if all vertices are reachable from v. In the step 4, we check if all vertices can reach v (In the reversed graph, if all vertices are reachable from v, then all vertices can reach v in the original graph).

venereology answered 11 months ago

Next > < Previous

Related Solutions

Prove that \strongly connected" is an equivalence relation on the vertex set of a directed graph

Create Kernel of a Strongly Connected Components using Kosaraju's Algorithm in Java. I have to create...

Create Kernel of a Strongly Connected Components using Kosaraju's Algorithm in Java. I have to create a Kernel DAG using the Strongly Connected Components found using Kosaraju's Algorithm. The input to the code is in the format. 5 \n 5 \n 1 0 \n 0 2 \n 2 1 \n 0 3 \n 3 4 The code will find the SCCs and print them to the screen, however, I need to find a way to construct a kernel based on...

Give an algorithm that constructs an undirected connected graph, which allows for labeling of the n...

Give an algorithm that constructs an undirected connected graph, which allows for labeling of the n vertices u - v <= k for every edge (u,v), where k is some constant. All nodes have a unique label.

Suppose T is a minimal spanning tree found by Prim’s algorithm in a connected graph G....

Suppose T is a minimal spanning tree found by Prim’s algorithm in a connected graph G. (i) Show that either T contains the n-1 smallest edges, or the n-1 smallest edges form a subgraph which contains a cycle. (ii) Show that if an edge (a, b) is not in T and if P is the unique path in T from a to b, then for each edge e in P the weight of e is less than the weight of...

A DAG is a directed graph that contains no directed cycles. Define G = (V, E)...

A DAG is a directed graph that contains no directed cycles. Define G = (V, E) in which V is the set of all nodes as {v1, v2, ..., vi , ...vn} and E is the set of edges E = {ei,j = (vi , vj ) | vi , vj ∈ V} . A topological order of a directed graph G = (V, E) is an ordering of its nodes as {v1, v2, ..., vi , ...vn} so that...

Write an algorithm to determine if two binary trees are identical when the ordering of the...

Write an algorithm to determine if two binary trees are identical when the ordering of the subtrees for a node is ignored. For example, if a tree has root node with value R, left child with value A and right child with value B, this would be considered identical to another tree with root node value R, left child value B, and right child value A. Make the algorithm as efficient as you can. Analyze your algorithm’s running time. How...

Assume the input graph is directed but may or may not have cycle in it, that...

Assume the input graph is directed but may or may not have cycle in it, that is, may or may not be a directed acyclic graph. Consider the recursive topological sorting algorithm shown below. TopologicalSort(G) { If G has only one node v then return v. Find a node v with no incoming edge and remove v from G. Return v followed by the order returned by TopologicalSort(G). } (a) Extend the recursive algorithm shown below so it can detect...

Is it always possible to make an undirected graph with two connected components connected by adding...

Is it always possible to make an undirected graph with two connected components connected by adding a single edge? • Why or why not? (Proof or counter example) [if true, give a proof, if false, give counter example] • Does the same hold true for directed graphs (and strongly connected components rather than connected components)? (Proof or counter example) [if true, give a proof, if false, give counter example]

Give an algorithm to detect whether a given undirected graph contains a cycle. If the graph...

Give an algorithm to detect whether a given undirected graph contains a cycle. If the graph contains a cycle, then your algorithm should output one. (It should not output all cycles in the graph, just one of them.) The running time of your algorithm should be O(m + n) for a graph with n nodes and m edges.

Construct a connected undirected graph with 25 or more nodes. - Draw your graph in a...

Construct a connected undirected graph with 25 or more nodes. - Draw your graph in a diagram. - Draw the adjacency matrix of your graph. - Draw the adjacency list of your graph. - Run the BFS algorithm on your graph and complete the chart discussed in class. Detailed steps, including the changes of node color, predecessor, etc., as discussed in class, are required.

Subjects