Алгоритм генерации графов и деревьев

@Даниил Кобицкой · Регистрация: 26.12.2018

Студворк — интернет-сервис помощи студентам

Добрый день. Подскажите пожалуйста алгоритм генерирования графов и деревьев и как это реализовать в программе? На форумах и всяких источниках никакой информации я не нашел...

@V_Monomax · 05.09.2019, 10:10

вообще алгоритм известен уже очень давно! Осталось создать под него соответствующие структуры в шарпе, если вы берете алгоритм другой, то подскажите.
А так я бы начал с того что создал бы вершину

C#
1
2
3
4
5
6
7
8
9
10
 public class TopGraph
{  
  public int TopNumber {get;set;} =0;//здесь может быть любая информация связанная с координатами графа
  public GraphArc FirstArc {get;set;}
  public GraphArc SecondArc {get;set;}
//необходимое и возможное количество связей
//или можно так:
  public List<GraphArc> Arcs {get;set;}
 
}

и соответственно дугу

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class GraphArc
{
   public TopGraph Parent {get;set;}
   public TopGraph Child {get;set;}
 //необходимое и возможно количество вершин между которыми могут быть связи
  public DirectGraph Direct {get;set;} =DirectGraph.NoDirect;
}
public enum DirectGraph
{
   NoDirect,
   UpToDown,
   DownToUp,
   LeftToRight,
...
}

Вот что-то такое у вас должно получиться в начале.
Все ли здесь понятно?

@Logovas · 23.02.2021, 17:01

Доброго дня!
Хотел бы воскресить топик)

Инфа всё же какая-то есть.
Но быть может кто-то поделится ссылочкой на алгоритм заполнения графа?

Заранее благодарен!

@ZoAs · 24.02.2021, 15:34

Logovas, нужно конкретизировать задачу. Сгенерировать случайный граф довольно просто. Получаем случайное число n - количество вершин (в нужном диапазоне). Создаем массив A[n, n] - матрицу смежности. Заполняем массив единицами и нулями случайным образом, вот граф и готов.

Когда мне понадобилось генерировать графы, я ничего даже искать не стал, а сразу сел писать алгоритм под свои нужды. Нужен только граф или ещё и его изображение, которое ещё и выглядит красиво? Нужно ли, чтобы граф был связным? Нужно ли иметь возможность указывать диапазоны для количества вершин, ребер, степеней вершин, радиуса и диаметра графа? Должен ли граф быть планарным? Если важно изображение графа, то должен ли граф быть плоским или будет ограничение на количество пересечений ребер? А может ещё нельзя допускать наложения ребер на ребра, ребер на вершины.

В общем, я бы выделил такие группы вопросов:
1) важно ли то, каким будет изображение графа
2) граф ориентированный или нет
3) какие характеристики графа должны быть настраиваемыми

@Logovas · 25.02.2021, 10:59

Сообщение от ZoAs

В общем, я бы выделил такие группы вопросов:
1) важно ли то, каким будет изображение графа
2) граф ориентированный или нет
3) какие характеристики графа должны быть настраиваемыми

1) Изображения не будет, соответственно не важно
2) Не ориентированный, не взвешенный
3) 50% всех вершин имеют связи от 0 до 100 со случайными вершинами
40% всех вершин имеют связи от 10 до 1000 со случайными вершинами
10% всех вершин имеют связи от 1000 до 10000 со случайными вершинами

Есть ещё особенность - размер графа, например на 10 миллионов нод. Решил, что хранить буду в списке смежных вершин, как мне показалось, так удобнее.

Пока на третье условие написал 3 отдельных метода, которые случайным образом берут вершины и связывают их со случайными вершинами по заданным условиям.

Всё же странно, задача вроде распространённая, а готового алгоритма я не нашел.

@ZoAs · 25.02.2021, 14:58

Logovas, можно примеры областей, в которых пригодится эта задача?
Может задача и распространенная, только требования скорее всего весьма уникальные всегда.

Наверное стоило более формализовать требования. Может нормальное распределение степеней вершин, к примеру. Не буду претендовать на такую строгость, попробую написать, что получится. Получилось так себе, требования не выполнил

Создадим класс. Поле vertexMap для перемешивания/переименования вершин, изначально будет заполнено самими индексами, в общем это перестановка. Массив adjList - это то, что вам нужно. Для каждой вершины этот массив хранит множество её соседей.

C#
1
2
3
4
5
6
class Graph
{
    int vCount;
    HashSet<int>[] adjList;
    int[] vertexMap;
}

Конструктор обычный.

C#
1
2
3
4
5
6
7
8
9
10
public Graph(int vCount = 10)
{
    this.vCount = vCount;
    adjList = new HashSet<int>[vCount];
    for (int v = 0; v < vCount; v++)
        adjList[v] = new HashSet<int>();
    vertexMap = new int[vCount];
    for (int i = 0; i < vCount; i++)
        vertexMap[i] = i;
}

Чтобы было понятнее, как работает vertexMap, добавим получение значений из матрицы смежности.

C#
1
2
3
4
5
6
7
8
public int Count
{
    get => vCount;
}
public bool this[int v, int u]
{
    get => adjList[vertexMap[v]].Contains(vertexMap[u]);
}

Метод добавления ребер для удобства.

C#
1
2
3
4
5
private void MakeEdge(int v, int u)
{
    adjList[vertexMap[v]].Add(vertexMap[u]);
    adjList[vertexMap[u]].Add(vertexMap[v]);
}

Дальше можно через конструктор добавить каких-нибудь ребер и проверить, как это будет работать.

Вывод матрицы смежности для тестов

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static void Main(string[] args)
{
    Graph graph = new Graph();
 
    Console.Write("\t");
    for (int u = 0; u < graph.Count; u++)
        Console.Write($" {u}");
    Console.WriteLine("\n");
    for (int v = 0; v < graph.Count; v++)
    {
        Console.Write($"{v}\t");
                
        for (int u = 0; u < graph.Count; u++)
            if (graph[v, u]) Console.Write($" 1");
            else Console.Write($" 0");
        Console.WriteLine();
    }
}

Я хочу использовать следующую идею в алгоритме. Пройдемся по 10% вершин и соединим их случайным образом с 1000-10000 других вершин (которые ещё не обрабатывали). При этом после прохода по каждой будем переупорядочивать вершины так, чтобы следующей обрабатывалась такая, у которой максимальная степень (без учета обработанных). Это для того, чтобы не получилось, что после прохода по 10% вершин у нас ещё 5% оказались с большими степенями (хоть это и маловероятно).
Потом повторим процедуру для ещё 40% вершин, но будем соединять их с 10-1000 других вершин.
И потом аналогично ещё с оставшимися 50%, давая им степени от 0 до 100. Хотя может к началу этого шага у них уже будут слишком большие степени, в некоторых тестах при небольшом количестве вершин так и получается.

Сортировку вершин (по сути переименование) в порядке уменьшения их степеней будем осуществлять путем сортировки массива vertexMap. Для этого вызываем Array.Sort(vertexMap, Compare);, где метод сравнения реализован как описано ниже. Правда я не уверен, как работает эта сортировка, здесь бы стоило применять такую, которая хороша для почти отсортированных массивов. На этом этапе стоит вывести матрицу смежности до и после сортировки, чтобы проверить правильность работы.

C#
1
2
3
4
5
6
7
8
9
private int Compare(int v1, int v2)
{
    if (adjList[v1].Count < adjList[v2].Count)
        return 1;
    else if (adjList[v1].Count > adjList[v2].Count)
        return -1;
    else
        return 0;
}

Итак, первый этап генерации. Обрабатываем первые 10% вершин. Для каждой случайным образом определяем степень. Если с текущей вершиной уже какие-то ранее соединяли, то из сгенерированного числа вычитаем степень, которая уже есть - adjList[vertexMap[v]].Count. И набираем нужное количество соседей, создавая ребра с вершинами, которые ещё не являются смежными для текущей и которые при этом ещё не обработаны. Работает безумно долго.

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void genGraph()
{
    Random random = new Random(047);
    for (int v = 0; v < vCount / 10; v++)
    {
        int valency = random.Next(1000, 10000) - adjList[vertexMap[v]].Count;
        while (valency > 0)
        {
            int u = random.Next(v + 1, vCount);
            if (adjList[vertexMap[v]].Contains(vertexMap[u]) == false)
            {
                MakeEdge(v, u);
                valency--;
            }
        }
        Array.Sort(vertexMap, Compare);
    }
}

А ещё памяти требует безумно много. Для миллиона вершин надо хранить в среднем номера 5500 соседей. Это 55e8 чисел. Если тип int32 (int16 не хватит), то уже немного больше 20 Гб. А ведь есть ещё накладные расходы на используемые структуры.
Для 40% и 50% нужно меньше соседей, так что порядок необходимого объема памяти останется тот же, полагаю. Не уверен, это на грани доступных для домашнего ПК объемов ОЗУ или выйдет гораздо больше. Для чего понадобился такой большой граф?)

Сократить время работы можно вызывая сортировку пореже. Либо с определенной периодичностью, либо случайным образом с заданной вероятностью. Ведь всё равно ситуация со степенями не может сильно измениться после добавления соседей для одной вершины. Можно даже пузырьковую сортировку использовать, не будет "черепах".

Выполнил прогон алгоритма для 10 тысяч вершин, требуя для 10% степени 100-1000, для 40% 10-100, для 50% 0-10. Когда обработали первые 10% вершин, у остальных, в среднем, уже получилась какая-то степень. Судя по всему 65. Когда после этого готовим следующие 40%, если генератор случайных чисел выдаст числа меньше 65 (точнее меньше текущей степени вершины), то ничего не поделать - степень останется 65. В итоге распределение количества вершин выйдет не таким, как хотелось бы.
Вывод: при такой генерации вершин, без интересного алгоритма, приходится надеяться на случайность. Или не столько на случайность, сколько на поставленные требования. Попытался менять условия, не получилось получить нужных процентов.

@ZoAs · 25.02.2021, 15:02

Старый файл приложил.
for (int v = vCount / 10; v < vCount / 40; v++) надо поменять на for (int v = vCount / 10; v < vCount / 2; v++), аналогично для 50% исправить диапазон. Причем для 50% я бы не перебирал все вершины.

@Logovas · 26.02.2021, 12:47

ZoAs, спасибо за столь детальное описание!
Интересный подход. Разбираюсь.

Граф будет использоваться для изучения распределения связей, построения аналитики.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11680&d=1772460536 Одним из. . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .
SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .

@Даниил Кобицкой 0 / 0 / 0 Регистрация: 26.12.2018 Сообщений: 7

	Алгоритм генерации графов и деревьев 04.09.2019, 15:28. Показов 9051. Ответов 7 Метки нет (Все метки) Добрый день. Подскажите пожалуйста алгоритм генерирования графов и деревьев и как это реализовать в программе? На форумах и всяких источниках никакой информации я не нашел... 0

@Logovas 19 / 16 / 10 Регистрация: 07.11.2015 Сообщений: 136
	23.02.2021, 17:01
	Доброго дня! Хотел бы воскресить топик) Инфа всё же какая-то есть. Но быть может кто-то поделится ссылочкой на алгоритм заполнения графа? Заранее благодарен! 0

@ZoAs 96 / 55 / 23 Регистрация: 01.05.2017 Сообщений: 78
	24.02.2021, 15:34
	Logovas, нужно конкретизировать задачу. Сгенерировать случайный граф довольно просто. Получаем случайное число n - количество вершин (в нужном диапазоне). Создаем массив A[n, n] - матрицу смежности. Заполняем массив единицами и нулями случайным образом, вот граф и готов. Когда мне понадобилось генерировать графы, я ничего даже искать не стал, а сразу сел писать алгоритм под свои нужды. Нужен только граф или ещё и его изображение, которое ещё и выглядит красиво? Нужно ли, чтобы граф был связным? Нужно ли иметь возможность указывать диапазоны для количества вершин, ребер, степеней вершин, радиуса и диаметра графа? Должен ли граф быть планарным? Если важно изображение графа, то должен ли граф быть плоским или будет ограничение на количество пересечений ребер? А может ещё нельзя допускать наложения ребер на ребра, ребер на вершины. В общем, я бы выделил такие группы вопросов: 1) важно ли то, каким будет изображение графа 2) граф ориентированный или нет 3) какие характеристики графа должны быть настраиваемыми 0

@ZoAs 96 / 55 / 23 Регистрация: 01.05.2017 Сообщений: 78
	25.02.2021, 15:02
	Старый файл приложил. `for (int v = vCount / 10; v < vCount / 40; v++)` надо поменять на `for (int v = vCount / 10; v < vCount / 2; v++)`, аналогично для 50% исправить диапазон. Причем для 50% я бы не перебирал все вершины. 1

@Logovas 19 / 16 / 10 Регистрация: 07.11.2015 Сообщений: 136
	26.02.2021, 12:47
	ZoAs, спасибо за столь детальное описание! Интересный подход. Разбираюсь. Граф будет использоваться для изучения распределения связей, построения аналитики. 0