Jak w temacie, kompletnie nie wiem jak sie do tego zabrać, temat widzę, że był poruszany na forum jednak znalezione w necie kody nic mi nie mówią.
Nie pogardzę gotowym kodem.
0
0
- Losujesz dowolny węzeł i wrzucasz do kolekcji S
- Pozostałe węzły wrzucasz do kolekcji L
- Losujesz węzeł Wy z kolekcji S oraz węzeł Wx z kolekcji L
- Łączysz wylosowane węzły Wy,Wx krawędzią
- Przerzucasz węzeł Wx do kolekcji S
- Jeżeli kolekcja L nie jest pusta wróć do punktu 3.
Masz wylosowane minimalne drzewo rozpinające, możesz dolosować jeszcze kilka krawędzi.
0
Dowolnego grafu? Skierowanego/Nieskierowanego? Ma spełniać jakieś dodatkowe własności?
To co podajesz w takiej wersji jest trywialne. Najprostszy spójny graf o N wierzchołkach to po prostu na przykład
A <-> B <-> C <-> D <-> E ... <-> Z
(gdzie A, B, C... to wierzchołki, a <-> to krawędzie).
Jeśli graf ma mieć element losowy, można następnie pododawać (dużo) losowych krawędzi.
Jeśli nie pogardzisz gotowym kodem
to proszę, ciekawe czy Ci w czymś pomoże ;].
struct node {
vector<int> edges;
};
int main() {
int n = 10;
vector<node> graph(n);
for (int i = 0; i < n - 1; i++) {
graph[i].edges.push_back(i + 1);
graph[i + 1].edges.push_back(i);
}
}