I trying to solve the following problem in $O(n^2)$:

We have vertices which represents cities and a textfile containing an edge on each line. How many roads do we need to build to make the graph connected - you can travel by road to each city?

Basically, at the start, we have just the vertices. As we read the textfile, we add a new edge each time we read a new line and we should decide after how many edges added is our graph now connected.

An example: An example: we have 5 vertices, A, B, C, D, E. In the textfile, we have defined these edges: A-B, B-C, A-C, B-D, C-D, A-D, B-E, C-E. The graph have been made connected after building 7 edges, while we have only 5 vertices when we start (5 components).

I solved it the following way: I'm calling the BFS algorithm after adding each edge to the graph until the graph is connected and counting the number of BFS calls. However, since the BFS itself has a time complexity of $O(n^2)$ and I'm calling it n-times, I have a worstcase time complexity near $O(n^3)$.

How would I solve this issue in $O(n^2)$?

  • $\begingroup$ I don’t think I understand the question. Are we looking for a minimum subset of edges in the text file to connect all cities? Or are we looking for the minimum number of edges in addition to those in the text file to connect all cities? $\endgroup$ – Throckmorton Aug 18 '19 at 6:53

You can do one graph traversal to find all the connected components of your graph.

Then add an edge from each connected component to the next : the graph is fully connected and you did only one traversal, that's $O(n^2)$

| cite | improve this answer | |
  • $\begingroup$ Not sure I follow. I start with only vertices defines, and then I have a textfile with each line containing a new edge to add. At the start, there are no edges. $\endgroup$ – Jack Aug 16 '19 at 11:10
  • $\begingroup$ So you have a set of edges, and you want a subset of these edges that induces a connected graph ? Are you looking for a spanning tree ? $\endgroup$ – GBat Aug 16 '19 at 12:38
  • $\begingroup$ @GBat Kinda, but it's not really a set, as the index of those edges matter too. Look at my example in the post. We have multiple roads being built and not all of those roads must contribute to the "connectivness". The edges that will be build are already defined in my input file. You can think of it like a spanning tree, but it may not be minimal, as there may be extra edges if the input file says so. We just have to decide after which edge will the graph be connected, if ever. Do you understand? $\endgroup$ – Jack Aug 16 '19 at 12:47
  • $\begingroup$ And also the order in which the edges are being built is already defined in my input text file, for an example: A-B, B-C, D-E means, that will will be built edge A-B, then edge B-C and so on.. $\endgroup$ – Jack Aug 16 '19 at 12:53
  • $\begingroup$ Yes, now I get it. Are you familiar with the union-find (also know as disjoint sets) data structure ? $\endgroup$ – GBat Aug 16 '19 at 12:59

I'm assuming that the problem is as follows. You're given the (ordered) list of edges in the input file and you read them one at a time and add them to the graph. You must stop as soon as the graph you've built is connected.

In that case, a simple $O(n^2)$ solution is to label each vertex with an integer that indicates what component it's in. Initially, the vertices are labelled $1, \dots, n$, since there are no edges so each vertex is its own component. Then, each time you add an edge, say between vertices $i$ and $j$ with labels $\ell_i$ and $\ell_j$, update every vertex with label $\ell_i$ to have label $\ell_j$. While you're doing that, check to see if there's some vertex that has a label different from $\ell_i$ and $\ell_j$. When every vertex has the same label, the graph is connected.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.