Графическое представление набора объектов называется графом.
Графы представляют собой нелинейную структуру данных, состоящую из узлов и ребер. Узлы и ребра иногда называют вершинами, а ребра — это линии или дуги, соединяющие два узла.
Это точное представление структуры данных графа.
Графики используются для решения многих реальных задач. Графики используются для представления сетей. Сети могут включать в себя пути в городской или телефонной сети, или кольцевой сети. Графики также используются в социальных сетях, таких как 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 вершин.