Матрица смежности - это способ представления графа 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()
