Let A be the language consisting of all strings representing undirected graphs t

Question

Let A be the language consisting of all strings representing undirected graphs
that are connected. Recall that a graph is connected if every node can be reached
from every other node by traveling along the edges of the graph. We write
A = {(G)I G is a connected undirected graph}.

The following is a high-level description of a TM M that decides A:
M = "On input (G), the encoding of a graph G:
1. Select the first node of G and mark it.
2. Repeat the following stage until no new nodes are marked:
3. For each node in G, mark it if it is attached by an edge to a
node that is already marked.
4. Scan all the nodes of G to determine whether they all are
marked. If they are, accept; otherwise, reject."

Question: Find the runtime of the algorithm determining whether an input graph is connected. Express this runtime in big-O notation. Does this algorithm run in polynomial time? No justification is needed.

Explanation / Answer

Let the graph have V nodes and E edges.

the runtime of the algorithm determining whether an input graph is connected is (2*E+V)*V

In terms of Big Oh this is (E+V)*V

And the algorithm clearly runs in polynomial time.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.