CODEWITHSUNDEEP
algorithmgraphtraversal
Geir
Geir

Reputation: 59

How do I find the minimum extra amount of edges needed to complete a connection?

Let's say we have been given the number of nodes and edges, N and M respectively. And then we are given which of the nodes are connected.How do we find the minimum amount of extra edge(s) needed to complete the connection, so that you can visit every node? By finding the answer you should be able to traverse to every node, by either going directly or going through another node to get to the goal.

Example on input:

4 2 (Nodes and edges)

0 1 (node 0 and node 1 is connected)

2 3 (node 2 and node 3 is connected)

Which then should give us the answer 1, we need one extra edge to complete the connection.

Upvotes: 0

Views: 280

Answers (2)

Edgar Rokjān
Edgar Rokjān

Reputation: 17483

All that you need is:

1) Find connected components. It can be done by dfs or bfs. In your example these components are 0, 1 and 2, 3 respectively.

2) Then you need to iterate through the all components and connect any two vertexes for every two consequtive components. In this way you connect first and second components, then second and third components and so on... In your example you can connect any of vertexes 0, 1 with any of vertexes 2, 3. For example, you can connect vertexes 0 and 2.

It's easy to see that if the total number of components is equal to C then the answer will be C - 1 additional edges.

Upvotes: 3

0gap
0gap

Reputation: 21

The minimum number of connections needed in order for your graph to be connected is N-1. But this holds if there are no nodes with 0 connections.

Try and picture a path resembling the connected list design. Every node has a degree of exactly 2, except from the two ends. That way (let's suppose your connection are not directed), starting from any node, you can reach your target by simply visiting the next not already visited node.

If M>N-1 then you can search for nodes that have more connections than needed and carry on from there.

Try and count the extra connections and compare it with the minimum number needed(N-1).

Upvotes: 0

Related Questions