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

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