Генерация случайных вершин

Question

Генерация случайных вершин

Как генерировать случайные числа, скажем, в диапазоне 0 - 100 когда пользователь указывает количество необходимых вершин. Я реализовал это для ребер ниже, но аналогичная вещь требуется для вершин. Как это может вписаться в существующую структуру ниже? :

int main(int argc, char *argv[]) {
// input number of vertices and edges
int V, E;
cin >> V >> E;

// check for maximum number of possible edges (disallow anti-parallel arcs)
if (E > V*(V-1)/2) {
E = V*(V-1)/2;
}

// construct random weighted graph
vector<vector<int> > G(V, vector<int>(V, 0));
for (int i = 0; i < E; i++)
while (true) {
const int u = rand() % V,
v = rand() % V;

// no self loops
if (u != v)
// disallow anti-parallel edges and overwriting existing arcs
if (0 == G[v][u] && 0 == G[u][v]) {
G[u][v] = rand() % 100;
break;
}
}// union-find sets are implemented inside the arrays
vector<int> parent(V, 0), depth(V, 0);

// at the start, all nodes point to themselves
for (int i = 0; i < V; i++) {
parent[i] = i;
depth[i] = 0;
}

// load all edges into priority queue, smallest weight on top of max-heap
priority_queue<PairPQ<int, int> > PQ;
for (int u = 0; u < V; u++)
for (int v = 0; v < V; v++)
if (G[u][v])
PQ.push(PairPQ<int, int>(u, v, -G[u][v]));

// keep track of MST edges
set<int> MSTedges;

// loop over all edges in ascending order of weight
while (!PQ.empty()) {
// no need for lazy decrease key idiom here!
const int u = PQ.top().item().first,
v = PQ.top().item().second;
// (don't care about rank/weight, note too that direction does not matter)
PQ.pop();

// check for edge between disjoint sets
if (find_set(u, parent) != find_set(v, parent)) {
MSTedges.insert(u * V + v);
union_set(u, v, parent, depth);
}
}

Где нужны случайные вершины:

  // printing MST graph in GraphViz format
*cout << endl
<< "digraph G {" << endl
<< "node [shape=circle]" << endl;
for (int i = 0; i < V; i++)
for (int j = i+1;j < V; j++) {
const int w = max(G[i][j], G[j][i]);
if (w) {
cout << "  " << j <<" -> " << i
<< " [label=\"" << w << "\"";
if (MSTedges.count(i * V + j) || MSTedges.count(j * V + i))
cout << ",color=red";
cout << "];" << endl;
}

}
cout << "}" << endl;
exit(0);*
}

Случайные числа, которые будут сгенерированы, являются узлами.

1

c++minimum-spanning-tree random

Решение

Другие решения

Ну, это просто вопрос использования std::uniform_real_distribution (при условии, что вы хотите равномерное распределение в диапазоне 0-100):

int n; // ... populate from input
std::vector<int> numbers(n);

std::random_device rd;
std::mt19937 gen(rd());
std::uniform_real_distribution<int> dis(0, 100);

for (int i = 0; i < n; ++i)
numbers.push_back(dis(gen));

for (int i : numbers)
// output i

0

Источник

Accepted Answer

Этот код должен примерно соответствовать нужному формату, я предоставляю C ++ 11 Решение с использованием случайный заголовок а также uniform_int_distribution с живой пример который должен быть предпочтительным, если это возможно:

#include <iostream>
#include <random>
#include <cstdlib>

int main()
{
std::random_device rd;

std::mt19937 e2(rd());

int V = 10 ;

std::uniform_int_distribution<int> dist1(0, V);for (int i = 0; i < V; ++i)
{
for (int k = i+1; k < V; ++k)
{
int index1 = dist1(e2) ;
int index2 = dist1(e2) ;
std::cout << "( " <<  index1 << " , " << index2 << ") " ;
}
std::cout << std::endl ;
}
std::cout << std::endl ;
}

Я также предоставляю код, используя rand а также чья формула основана на Как я могу получить случайные целые числа в определенном диапазоне? запись от C FAQ живой пример:

#include <iostream>
#include <cstdlib>

int main()
{
int V = 10 ;

for (int i = 0; i < V; ++i)
{
for (int k = i+1; k < V; ++k)
{
int index1 = rand() / (RAND_MAX / V  + 1) + 1 ;
int index2 = rand() / (RAND_MAX / V + 1) + 1;
std::cout << "( " <<  index1 << " , " << index2 << ") " ;
}
std::cout << std::endl ;
}
std::cout << std::endl ;
}

1