Size: a a a

2020 June 08

V🇺

Vladislav 🇺🇸🚜🇷🇺... in pro.algorithms
Dmi Tgl
Добрый день. Где можно детально почитать про то .как реализовать красно-черное дерево?
вот тут неплохое описание (более простого для реализации варианта) красно-черного дерева
https://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf
источник

 P

 ‌‌Gleb Pilipets... in pro.algorithms
У кормена же есть
источник

 P

 ‌‌Gleb Pilipets... in pro.algorithms
источник

DT

Dmi Tgl in pro.algorithms
Kotomord_λapki
В гроках было вроде
у меня кстати есть какая-то книга про гроки алгоритмов, посмотрел - там не нашел, в оглавлении в смысле, может книжка не та
источник

DT

Dmi Tgl in pro.algorithms
Спасибо, щас заценю весь материал
источник

0

0xFF in pro.algorithms
Задача. Сгенерировать граф в виде матрицы смежности с V вершинами и E рёбрами.

Тогда мой цикл должен выглядеть так?
degree = e/2;
for (size_t i = 0; i < vertexes; i++)
{
 for (size_t j = 0; j < degree; j++)
 {
  size_t to = getNumber(i);
  if (adjMatrix[i][to] != 1 and adjMatrix[to][i] != 1) {
   adjMatrix[i][to] = adjMatrix[to][i] = 1;
  }
 }
}
источник

DT

Dmi Tgl in pro.algorithms
0xFF
Задача. Сгенерировать граф в виде матрицы смежности с V вершинами и E рёбрами.

Тогда мой цикл должен выглядеть так?
degree = e/2;
for (size_t i = 0; i < vertexes; i++)
{
 for (size_t j = 0; j < degree; j++)
 {
  size_t to = getNumber(i);
  if (adjMatrix[i][to] != 1 and adjMatrix[to][i] != 1) {
   adjMatrix[i][to] = adjMatrix[to][i] = 1;
  }
 }
}
Ребра одним числом задаются?
источник

DT

Dmi Tgl in pro.algorithms
Енто странно
источник

CD

Constantine Drozdov in pro.algorithms
0xFF
Задача. Сгенерировать граф в виде матрицы смежности с V вершинами и E рёбрами.

Тогда мой цикл должен выглядеть так?
degree = e/2;
for (size_t i = 0; i < vertexes; i++)
{
 for (size_t j = 0; j < degree; j++)
 {
  size_t to = getNumber(i);
  if (adjMatrix[i][to] != 1 and adjMatrix[to][i] != 1) {
   adjMatrix[i][to] = adjMatrix[to][i] = 1;
  }
 }
}
Я знаю примерно десяток способов, в каком смысле это может быть понято)
источник

DT

Dmi Tgl in pro.algorithms
Constantine Drozdov
Я знаю примерно десяток способов, в каком смысле это может быть понято)
Это что за десятки смыслов в генерации графа в виде матрицы смежности?
источник

DT

Dmi Tgl in pro.algorithms
Я кстати понял как енто делается
источник

DT

Dmi Tgl in pro.algorithms
Точнее что нужно
источник

CD

Constantine Drozdov in pro.algorithms
Dmi Tgl
Это что за десятки смыслов в генерации графа в виде матрицы смежности?
Ну например, можно требовать равновероятности всех таких матриц смежности
источник

CD

Constantine Drozdov in pro.algorithms
Это будет задача о генерации сочетания
источник

DT

Dmi Tgl in pro.algorithms
Тут скорее всего обычный граф
источник

CD

Constantine Drozdov in pro.algorithms
А чем результат не обычный граф?
источник

DT

Dmi Tgl in pro.algorithms
По типу
Введите смежные вершины для вершины 1
источник

0

0xFF in pro.algorithms
Крч, я придумал алгоритм.

Кидаю по единичке в случайную позицию в строке матрицы.
Индекс случайной позиции лежит в интервале (i+1, V - 1);
Получим вот такой граф: При V = 6; E = 12;
0 0 0 1 0 0
0 0 0 0 0 1
0 0 0 0 0 1
1 0 0 0 0 1
0 0 0 0 0 1
0 1 1 1 1 0

Далее, получаю количество оставшихся вершин, беру 2 случайные, неравные, не смежные вершины, и докидываю оставшиеся рёбра.

В итоге получаю вот такой граф:
0 1 0 1 1 1
1 0 1 0 1 1
0 1 0 1 1 1
1 0 1 0 0 1
1 1 1 0 0 1
1 1 1 1 1 0

Как сделать такой граф в одном цикле?
источник

A(

Andrey (@AndrewB330) in pro.algorithms
0xFF
Крч, я придумал алгоритм.

Кидаю по единичке в случайную позицию в строке матрицы.
Индекс случайной позиции лежит в интервале (i+1, V - 1);
Получим вот такой граф: При V = 6; E = 12;
0 0 0 1 0 0
0 0 0 0 0 1
0 0 0 0 0 1
1 0 0 0 0 1
0 0 0 0 0 1
0 1 1 1 1 0

Далее, получаю количество оставшихся вершин, беру 2 случайные, неравные, не смежные вершины, и докидываю оставшиеся рёбра.

В итоге получаю вот такой граф:
0 1 0 1 1 1
1 0 1 0 1 1
0 1 0 1 1 1
1 0 1 0 0 1
1 1 1 0 0 1
1 1 1 1 1 0

Как сделать такой граф в одном цикле?
а в чем задача?
источник

0

0xFF in pro.algorithms
Сгенерировать связный неорграф без петель
источник