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

Алгоритм, матрица, 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

Комментарии

Только авторизованные пользователи могут публиковать комментарии.
Пожалуйста, авторизуйтесь или зарегистрируйтесь
Donate

Здравствуйте, уважаемые пользователи EVILEG !!!

Если сайт вам помог, то поддержите разработку сайта финансово, пожалуйста.

Вы можете сделать это следующими способами:

Спасибо, Евгений Легоцкой

SF
27 января 2020 г. 5:10
Sergei Filin

C++ - Тест 001. Первая программа и типы данных

  • Результат:73баллов,
  • Очки рейтинга1
БМ
25 января 2020 г. 13:16
Бекзод Муминов

C++ - Тест 001. Первая программа и типы данных

  • Результат:53баллов,
  • Очки рейтинга-4
БМ
25 января 2020 г. 13:04
Бекзод Муминов

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

  • Результат:20баллов,
  • Очки рейтинга-10
Последние комментарии
m
27 января 2020 г. 9:53
michaeldevp

Единственная проблема состоит в том, что для выделения QCheckBox приходится дважны нажимать мышь. Получается что сначала выделяется ячейка. а только потом фокус уже попадает на виджет. …
27 января 2020 г. 1:01
Ruslan Polupan

Да так, посмотрел библиотеку попробовал примеры...
s
26 января 2020 г. 14:51
shame

Чего не webassembly?
21 января 2020 г. 14:12
Docent

Полезная статья. Как всегда - то что надо. Добавлю ещё маленькую полезность - после установки tracer (88 строка) и перед выводом значений в lineEdit (91 строка) стоит добавить updatePositio…
17 января 2020 г. 2:31
Андрей Янкович

Выглядит как ошибка библиотеки. Расскажите подробно на какой платформе вы собираете проект (MinGW или MSVC) их версии и версии Qt.
Сейчас обсуждают на форуме
27 января 2020 г. 3:17
Илья Чичак

а почему бы не сделать одну модель, например Attachement со всеми этими полями, и в зависимости от действия пользователя, например, "добавить документ", "добавить картинку" и т.д. класть все это…
E
26 января 2020 г. 11:42
Edi

Другого способа, как получать перезагруженный контент через JavaScript на странице, я не знаю. Получилось сделать без QWebEngineView, с помощью QWebEnginePage, runJavaScrip…
E
26 января 2020 г. 11:14
Edi

Да, я не понял до конца того, как это работает, мало опыта работы с qt и QVAriant ни разу не использовал. Спасибо за помощь)
VZ
26 января 2020 г. 4:11
Vladimir Zhitkovsky

Да, спасибо порешалось таким образом: удаление одного for(int i = 0; i < lstData.count(); ++i){ auto *data= dynamic_cast<Data*>(lstData[i]); if(data) { if(…
14 января 2020 г. 9:04
Руслан Волшебник

Проблема осталась. Но я выснил, что это происходит когда файл достигает максимального размера.
EVILEG
О нас
Услуги
© EVILEG 2015-2019
Рекомендует хостинг TIMEWEB