Guidance needed with finding random graphs(trees) for testing

Правка en1, от GLAYS, 2019-10-21 17:59:10

Hello!

When I need to stress-test a problem on trees, I usually find a random tree like this:

int n = random(1, 100);
for(int i = 2; i <= n; ++i){
    p = random(1,i - 1);
    addEdge(p, i), addEdge(i, p);
}

As in; to find a random tree of $$$N$$$ nodes, I just find a random sequence $$$P$$$(parents) of length $$$N-1$$$ with each $$$1<=Pi<=i-1$$$ for each $$$2<=i<=N$$$.

And it worked well, or so I believed at least.

But I remember watching an Errichto stream(I think it's the AtCoder DP contest one) where he showed how he stress tests and then said that the previous method only prints a specific kind of trees, and that he recommends using Prüfer Sequences. I kept thinking about why that's true but found no answer online.

Of course, Prüfer Sequences are clearly the best and most trusted choice since it's proved that any sequence represents a unique tree and that any tree can be represented by a sequence(more info here). And though it's not that complicated, I still don't want to keep writing it whenever I need to, unless there's an important difference between the two methods.

So if anyone would enlighten me on the difference if it exists, that would be great :D (It would be good if it's Errichto too xd)

Any other advices/tricks on stress-testing graphs or in general would be awesome!

Thankss ^^

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский GLAYS 2019-10-21 17:59:10 1481 Initial revision (published)