CODEWITHSUNDEEP
c++kruskals-algorithm
Kajzer
Kajzer

Reputation: 2385

How do I generate a undirected graph in c++?

I have to generate simple undirected graph, to test my Kruskal's algorithm on it. I have a structure for all the connections, made like this:

    struct connection
    {
       node1;
       node2;
       edge_value;
    }

Now I need to generate a decent amount of these connections, to test Kruskal's on it. The Kruskal's algo wasn't this tough than this generation, maybe because this is the first time I am faced with Graphs.

Upvotes: 0

Views: 630

Answers (1)

fcsc
fcsc

Reputation: 111

Your data structure is ok, because you want to run the kruskal algorithm!

I assume that you have already the kruskal implementation (with this data-structure, the only thing you need to do is set up a vector and then sort that vector with a proper function and finally walk through that vector, having a computational cost of n log(n) ).

If you need to test your algorithm I will recommend looking into uva's website, from the top of my head I can refer you to this problem: http://uva.onlinejudge.org/external/113/11354.html You could use the 3 example cases to test if your kruskal implementation works..

Upvotes: 3

Related Questions