Матриця суміжності

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

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

Подання матриці суміжності

Розмір матриці VxV, де V - кількість вершин у графі, а значення запису Aij дорівнює 1 або 0, залежно від того, чи існує ребро від вершини до вершини j.

Приклад матриці суміжності

Зображення нижче показує графік та його еквівалентну матрицю суміжності.

У разі неорієнтованого графа матриця симетрична щодо діагоналі, тому що у кожного ребра (i, j) також є ребро (j, i).

Плюси матриці суміжності

Основні операції, такі як додавання ребра, видалення ребра та перевірка наявності ребра від вершини i до вершини j є надзвичайно ефективними за часом операціями. Операціями із постійним часом.

Якщо граф щільний і число ребер велике, матриця суміжності має стати першим вибором. Навіть якщо граф і матриця суміжності розріджені, ми можемо її уявити, використовуючи структури даних для розрідженої матриці.

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

Виконуючи операції над суміжною матрицею, ми можемо отримати важливу інформацію про природу графа та взаємозв'язок між його вершинами.

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

Через вимогу до простору матриці суміжності VxV може бути недостатньо пам'яті. Але зазвичай графи не мають занадто багато з'єднань, і це головна причина, чому списки суміжності є найкращим вибором для більшості завдань.

Хоча базові операції прості, такі операції, як вЕджах і вЕджах, дорогі при використанні подання матриці суміжності.

Код матриці суміжності

Якщо ви знаєте, як створювати двовимірні масиви, значить ви знаєте, як створити матрицю суміжності.

Матриця суміжності в 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()