Как создать случайный график в С++?

Граф — это тип нелинейной структуры данных, который имеет два типа компонентов «Вершины» (узлы) и «ребра». Он содержит набор вершин ( V ) и набор ребер ( E ). Две вершины графа соединены ребром. Граф обозначается через G(V, E) .

Способы представления графика:

Существует два основных способа представления графа в C++:

• Матрица смежности
• Список смежности

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

Матрица смежности:

Граф представляется в виде матрицы. Это матрица V * V , где V представляет количество вершин, присутствующих в графе.

Возьмем матрицу adj[][] . Если в ячейке adj[i][j] есть какое-либо значение, это означает, что существует ребро от i до j . Матрица смежности неориентированного графа всегда симметрична. Его можно использовать для представления взвешенного графа и невзвешенного графа . В невзвешенном графе adj[i][j] = 1, а во взвешенном графе adj[i][j] равно весу ребра.

Список смежности:

Это также распространенный метод представления графа. Пусть список будет array[] . Элемент array[i] представляет собой список вершин, смежных с i- ^й вершиной. Его также можно использовать для представления взвешенного графика. Когда он используется для представления взвешенного графа, веса ребер могут быть представлены в виде списков пар.

Создайте случайный график, используя матрицу смежности:

Для реализации выполните следующие шаги:

• Мы создаем функцию с именем GenRandomGraphs и передаем ей переменную. (переменная - количество ребер и вершин)
• Создавайте случайные ребра, пока не будут покрыты все возможные ребра.
  • Для каждого сгенерированного ребра проверьте, было ли это ребро сгенерировано ранее или оба конца ребра совпадают.
• После этого проходим для каждой вершины:
  • Найдите ребра, для которых текущая вершина является конечным узлом.
  • Вставьте это в список смежности для текущей вершины.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(E ² + E*V), где E — количество ребер, а V — количество вершин.
Вспомогательное пространство: O(V ² )

Статьи по Теме:

• Введение в график — учебные пособия по структурам данных и алгоритмам
• Граф и его представление