From what I can derive from your code, you don't have any means for entering a vertex that hasn't got at least one connection to another vertex.
An undirected graph consist of two sets of distinct information:
- Vertices
- Edges
I think you have one array of edges where the array index itself is the vertex label, and that's fine, as long you only ever need to represent connected vertices.
The most common and compact implementation of Kruskal's algorithm in C, employs a two dimension array as [vertices][edges]. Your code consists a one "graph" containing an array of edges.
A quick search online, turns up some examples, but they all seem to work with fully connected networks. Your assignment seems to include the requirement that the network is not fully connected, therefore; you require a means for entering and storing a vertex that is not connected to anything. In other words, you need to be able to add nodes to your graph that do not connect to anything else.
Based on your code, you might be able to create unconnected islands, but you'll have to be carful that those aren't directly or indirectly connected to V0. You'll also have to add code to detect those islands.
The first thing you need is a data set that has two or more island networks. The smallest island your code will let you create is a pair of vertices connected by one road. If you create that first, and then make sure none of the remaining edges that you define are connected to that first pair in any way, you'll have at least two islands.
Then you run your program and see what happens. It will probably fail, but now you've got a data set you can work with for testing changes to your code. We call this unit testing. You need two simple data sets. One fully connected set and one that has islands. You can store program inputs in a file and pipe them into your app:
inputPartiallyConnected.txt | YourApp
inputFullyConnected.txt | YourApp
Enter that into your program. The values on the left can be stored in a file. The bent arrows are carriage returns. Your code needs to recognize that 1 and 2 cannot be reached from any of the other nodes.
Here's the text:
6
1
8
3 8
1 2 10
3 4 11
5 6 6
4 6 7
5 4 5
5 4 1
6 3 2
You can create a fully connected version by adding a road between 2 and 4, or 1 and 3. Keep it simple.
Your Kruskal's algorithm implementation will not work correctly with multiple forests. The data set above is essentially two forests. You can prevent the user from inputting more than one forest by requiring every new edge, except the first one, includes at least one vertex that is referenced in one of the previously entered edges.
So
- for each new edge after the first one,
- for each vertex in the new edge,
- search all pervious edges for that vertex.
- If neither of them is found in the previous edges,
- then you could issue the "Insufficient" output and discard that bad edge,
- then prompt the user for input again.
- Rinse and repeat.
Since, in the above test data set, we enter 1--2 followed by 3--4, we should get an Insufficient warning for literally every edge that follows, because they do not contain either 1 or 2 in their vertex sets. So once you have code that successfully reject everything but 1--2 in the above list, you can then reorder it, such that you are always constructing a fully connected graph (aka: A single tree).
If your assignment was to accept a forest of trees, then you'll have to find the islands first, and run each of them separately through the Kruskal's algorthm.
