Графическое представление набора объектов называется графом.

Графы представляют собой нелинейную структуру данных, состоящую из узлов и ребер. Узлы и ребра иногда называют вершинами, а ребра — это линии или дуги, соединяющие два узла.

Это точное представление структуры данных графа.

Графики используются для решения многих реальных задач. Графики используются для представления сетей. Сети могут включать в себя пути в городской или телефонной сети, или кольцевой сети. Графики также используются в социальных сетях, таких как linkedIn, Facebook. Например, в Facebook каждый человек представлен вершиной (или узлом). Каждый узел представляет собой структуру и содержит такую ​​информацию, как идентификатор человека, имя, пол, регион и т. д.

Графические термины, с которыми необходимо ознакомиться:

  • Вершина — каждый узел графа представлен как вершина. В следующем примере помеченный круг представляет вершины. Таким образом, от A до G являются вершинами. Мы можем представить их с помощью массива, как показано на следующем рисунке. Здесь A можно идентифицировать по индексу 0. B можно идентифицировать по индексу 1 и так далее.
  • Edge — Edge представляет собой путь между двумя вершинами или линию между двумя вершинами. В следующем примере линии от A до B, от B до C и т. д. представляют ребра. Мы можем использовать двумерный массив для представления массива, как показано на следующем рисунке. Здесь AB может быть представлено как 1 в строке 0, столбце 1, BC как 1 в строке 1, столбце 2 и так далее, сохраняя другие комбинации как 0.
  • Смежность — два узла или вершины являются смежными, если они соединены друг с другом через ребро. В следующем примере B примыкает к A, C примыкает к B и так далее.
  • Путь — Путь представляет собой последовательность ребер между двумя вершинами. В следующем примере ABCD представляет собой путь от A до D.

  • Направленный граф: Граф, в котором ребро (u, v) не обязательно означает, что также существует ребро (v, u). Ребра в таком графе представлены стрелками, чтобы показать направление ребра.

Графическое представление:

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

  • Матрица смежности представляет собой двумерный массив M x M вершин. Каждая строка и столбец представляют собой вершину.
  • Если значение любого элемента A[i][j] равно 1, это означает, что существует ребро, соединяющее вершину i и вершину j.
  • Матрица смежности для графа, который мы создали выше, имеет вид

  • Поскольку это неориентированный граф, для ребра (0,2) нам также нужно пометить ребро (2,0); делая матрицу смежности симметричной относительно диагонали.
  • Поиск ребра (проверка наличия ребра между вершиной A и вершиной B) чрезвычайно быстр в представлении матрицы смежности, но мы должны зарезервировать место для каждой возможной связи между всеми вершинами (V x V), поэтому для этого требуется больше места.

2. Список смежности

  • Список смежности представляет граф как массив связанных списков.
  • Индекс массива представляет собой вершину, а каждый элемент в его связанном списке представляет другие вершины, образующие ребро с этой вершиной.
  • Список смежности для графа, который мы сделали в первом примере, выглядит следующим образом:

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

Основные операции с графиком:

  • Добавление вершины. Добавляет вершину на график:
  • Чтобы добавить вершину в граф, нам нужно увеличить как строку, так и столбец существующей матрицы смежности, а затем инициализировать новые элементы, связанные с этой вершиной, равными 0 (т. е. добавленная новая вершина не связана ни с какой другой вершиной).
  • Пример кода:
void addVertex()
{
//increasing the number of vertices
n++;int i;
//initialising the new elements with 0
for (int i=0;i<n;++i)
{
g[i][n-1]= 0;
g[n-1][i]= 0;
}
}
  • Добавление ребра: добавляет ребро между двумя вершинами графа.
  • Чтобы добавить ребра между двумя существующими вершинами, такими как вершина «x» и вершина «y», тогда элементам g[x][y] и g[y][x] матрицы смежности будет присвоено значение 1, что означает, что существует ребро между вершиной «x» и вершиной «y».
  • Пример кода:
void addEdge(int x, int y)
{
if((x>=n)||(y>n){ //checks if the vertex exists in the graph
cout<<”vertex does not exist”;
}
if(x==y){ //checks if the vertex is connecting to itself
cout<<”Connecting to itself”;
}
else{ //connecting the vertices
g[y][x]=1;
g[x][y]=1;
}
  • Отображение графика: график отображается с использованием матрицы смежности g[n][n] с количеством вершин n. Отображается двумерный массив (матрица смежности), в котором, если между двумя вершинами «x» и «y» есть ребро, тогда g [x] [y] равно 1, в противном случае 0.
  • Пример кода:
void displayAdjacencyMatrix()
{
cout << “\n\n Adjacency Matrix:”;
for (int i = 0; i < n; ++i) { // displaying the 2D array
cout << “\n”;
for (int j = 0; j < n; ++j) {
cout << “ “ << g[i][j];
}
}
}
  • Удаление вершины в графе. Чтобы удалить вершину из графа, нам нужно проверить, существует ли эта вершина в графе или нет, и если эта вершина существует, нам нужно сдвинуть строки влево. и столбцы выше матрицы смежности, так что значения строки и столбца данной вершины заменяются значениями следующей вершины, а затем уменьшают количество вершин на 1. Таким образом, эта конкретная вершина будет удалена из смежности матрица.
  • Пример кода:
void removeVertex(int x)
{
// checking if the vertex is present
if (x > n) {
cout << “\nVertex not present!”;
return;
}
else {
int i;
// removing the vertex
while (x < n) {
// shifting the rows to left side
for (i = 0; i < n; ++i) {
g[i][x] = g[i][x + 1];
}
// shifting the columns upwards
for (i = 0; i < n; ++i) {
g[x][i] = g[x + 1][i];
}
x++;
}
// decreasing the number of vertices
n — ;
}
}

Внимание: матрицы смежности занимают много места в памяти. Такие матрицы оказываются очень разреженными. Это представление требует места для n*n элементов, временная сложность метода addVertex() равна O(n), а временная сложность метода removeVertex() составляет O(n*n) для графа из n вершин.