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

Алгоритм, матрица, Matrix, Graph

Матрица смежности - это способ представления графа G = {V, E} в виде матрицы логических значений.

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

Размер матрицы VxV, где V - количество вершин в графе, а значение записи Aij равно 1 или 0, в зависимости от того, существует ли ребро от вершины i до вершины j.

Пример матрицы смежности

Изображение ниже показывает график и его эквивалентную матрицу смежности.

В случае неориентированного графа матрица симметрична относительно диагонали, потому что у каждого ребра (i, j) также есть ребро (j, i).

Плюсы матрицы смежности

Основные операции, такие как добавление ребра, удаление ребра и проверка наличия ребра от вершины i до вершины j, являются чрезвычайно эффективными по времени операциями. Операциями с постоянным временем.

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

Однако самое большое преимущество исходит от использования матриц. Последние достижения в области аппаратного обеспечения позволяют нам выполнять даже дорогостоящие матричные операции на графическом процессоре (GPU).

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

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

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

Хотя базовые операции просты, такие операции, как inEdges и outEdges, дороги при использовании представления матрицы смежности.

Код матрицы смежности

Если вы знаете, как создавать двумерные массивы, значит вы также знаете, как создать матрицу смежности.

Матрица смежности в C++

#include <iostream>
using namespace std;
class Graph {
private:
      bool** adjMatrix;
      int numVertices;
public:
      Graph(int numVertices) {
            this->numVertices = numVertices;
            adjMatrix = new bool*[numVertices];
            for (int i = 0; i < numVertices; i++) {
                  adjMatrix[i] = new bool[numVertices];
                  for (int j = 0; j < numVertices; j++)
                        adjMatrix[i][j] = false;
          }
    }

      void addEdge(int i, int j) {
                  adjMatrix[i][j] = true;
                  adjMatrix[j][i] = true;
    }

      void removeEdge(int i, int j) {
                  adjMatrix[i][j] = false;
                  adjMatrix[j][i] = false;
    }

      bool isEdge(int i, int j) {
                  return adjMatrix[i][j];
    }
    void toString() {
      for (int i = 0; i < numVertices; i++) {
                  cout << i << " : ";
                  for (int j = 0; j < numVertices; j++)
                        cout << adjMatrix[i][j] << " ";
                  cout << "\n";
      }
    }

    ~Graph() {
            for (int i = 0; i < numVertices; i++)
                  delete[] adjMatrix[i];
            delete[] adjMatrix;
    }
};
int main(){
        Graph g(4);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.toString();
        /* Outputs
           0: 0 1 1 0 
           1: 1 0 1 0 
           2: 1 1 0 1 
           3: 0 0 1 0 
          */
}

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

public class Graph {
      private boolean adjMatrix[][];
      private int numVertices;

      public Graph(int numVertices) {
          this.numVertices = numVertices;
          adjMatrix = new boolean[numVertices][numVertices];
    }

      public void addEdge(int i, int j) {
                adjMatrix[i][j] = true;
                adjMatrix[j][i] = true;
    }

      public void removeEdge(int i, int j) {
                adjMatrix[i][j] = false;
                adjMatrix[j][i] = false;
    }

      public boolean isEdge(int i, int j) {
                  return adjMatrix[i][j];
    }
    public String toString() {
        StringBuilder s = new StringBuilder();
        for (int i = 0; i < numVertices; i++) {
            s.append(i + ": ");
            for (boolean j : adjMatrix[i]) {
                s.append((j?1:0) + " ");
            }
            s.append("\n");
        }
        return s.toString();
    }
    public static void main(String args[])
    {
        Graph g = new Graph(4);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);

        System.out.print(g.toString());
        /* Outputs
           0: 0 1 1 0 
           1: 1 0 1 0 
           2: 1 1 0 1 
           3: 0 0 1 0 
          */
    }
}

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

class Graph(object):
    def __init__(self, size):
        self.adjMatrix = []
        for i in range(size):
            self.adjMatrix.append([0 for i in range(size)])
        self.size = size
    def addEdge(self, v1, v2):
        if v1 == v2:
            print("Same vertex %d and %d" % (v1, v2))
        self.adjMatrix[v1][v2] = 1
        self.adjMatrix[v2][v1] = 1
    def removeEdge(self, v1, v2):
        if self.adjMatrix[v1][v2] == 0:
            print("No edge between %d and %d" % (v1, v2))
            return
        self.adjMatrix[v1][v2] = 0
        self.adjMatrix[v2][v1] = 0
    def containsEdge(self, v1, v2):
        return True if self.adjMatrix[v1][v2] > 0 else False
    def __len__(self):
        return self.size

    def toString(self):
        for row in self.adjMatrix:
            for val in row:
                print('{:4}'.format(val)),
            print

def main():
        g = Graph(5)
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);

        g.toString()

if __name__ == '__main__':
   main()
Рекомендуем хостинг TIMEWEB
Рекомендуем хостинг TIMEWEB
Стабильный хостинг, на котором располагается социальная сеть EVILEG. Для проектов на Django рекомендуем VDS хостинг.
Поддержать автора Donate

Комментарии

Только авторизованные пользователи могут публиковать комментарии.
Пожалуйста, авторизуйтесь или зарегистрируйтесь
Ищу работу?
25,000.00 руб. - 30,000.00 руб.
Разработчик Qt/C++
Barnaul, Altai Krai, Russia

Для зарегистрированных пользователей на сайте присутствует минимальное количество рекламы

СВ
23 октября 2019 г. 1:00
Семен Волох

C++ - Тест 004. Указатели, Массивы и Циклы

  • Результат:70баллов,
  • Очки рейтинга1
SS
22 октября 2019 г. 14:31
Samantha Smith

Qt - Тест 001. Сигналы и слоты

  • Результат:52баллов,
  • Очки рейтинга-4
МБ
21 октября 2019 г. 1:25
Михаил Булатов

C++ - Тест 002. Константы

  • Результат:16баллов,
  • Очки рейтинга-10
Последние комментарии
17 октября 2019 г. 2:17
Евгений Легоцкой

Используем, там где требуется :)
MP
17 октября 2019 г. 2:15
Mikhail Petrov

Совет: подключайте ресурсы динамически. Используйте Resource Compiler: https://doc.qt.io/qt-5/rcc.html
16 октября 2019 г. 6:45
Евгений Легоцкой

Если это не чистой воды спам, а по делу, то без проблем. Но в таком случае лучше создавайте отдельный вопрос на форуме . При создании вопроса есть поле, в котором можно указать статью…
КК
16 октября 2019 г. 6:39
Кирилл Кирилыч

А тут можно ссылки на сторонний ресурс показывать? Нашёл на habr похожую статью, только там чуток отличается код и про локальный сервер написано, нужно чтоб кто то понимающий посмотрел и своё …
Сейчас обсуждают на форуме
23 октября 2019 г. 4:06
Евгений Легоцкой

Ну если после обновления начало появляться, то тогда откатить драйвера. А вообще, если это жить не мешает и код работает как и раньше, то просто проигнорировать эти сообщения.
22 октября 2019 г. 2:42
Pavel K.

Всем привет , Пытаюсь реализовать класс для работы с блютуз (Bluetooth Handler) для мобилки , с использование QBluetoothDeviceInfo и QBluetoothDeviceDiscoveryAgent . Может у кого е…
22 октября 2019 г. 2:16
Pavel K.

попробуй сделать через свой собственный компонет , те возьми контрол Component, например , переорпедели как свой , в нем что нить типо проперти type : disk1, disk2 (сделай метод в структуре …
Е
22 октября 2019 г. 0:03
Евгений_Канусовский@1981

Этот алгоритм предназначен для того чтобы исключить из обработки строки содержащие буквенные символы. Если Вам не трудно опишите пожалуйста как бы Вы написали этот алгоритм, желательно в коде?
MP
21 октября 2019 г. 7:03
Mikhail Petrov

Зависит от вашей задачи. Можете обратить внимание на этот пример: https://doc.qt.io/qt-5/qtqml-referenceexamples-properties-example.html QQmlListProperty используется мною достаточно ч…
EVILEG
О нас
Услуги
© EVILEG 2015-2019
Рекомендует хостинг TIMEWEB