У цьому підручнику ви дізнаєтесь, що таке матриця суміжності. Крім того, ви знайдете робочі приклади матриці суміжності на мовах C, C ++, Java та Python.
Матриця суміжності - це спосіб представлення графа G = (V, E) як матриці булевих чисел.
Представлення матриці суміжності
Розмір матриці - це VxVде Vкількість вершин у графіку, а значення запису Aij- 1 або 0, залежно від того, чи є ребро від вершини i до вершини j.
Приклад матриці суміжності
На зображенні нижче показано графік та його еквівалентну матрицю суміжності.
Матриця суміжності з графіка
У випадку ненаправлених графіків матриця симетрична відносно діагоналі, оскільки кожне ребро (i,j)також має ребро (j,i).
Плюси матриці суміжності
Основні операції, такі як додавання ребра, видалення ребра та перевірка наявності ребра від вершини i до вершини j, надзвичайно ефективні в часі та постійні операції в часі.
Якщо графік щільний і число ребер велике, матриця суміжності повинна бути першим вибором. Навіть якщо графік і матриця суміжності розріджені, ми можемо представити його, використовуючи структури даних для розріджених матриць.
Однак найбільша перевага полягає в використанні матриць. Останні досягнення в області апаратного забезпечення дозволяють нам виконувати навіть дорогі матричні операції на графічному процесорі.
Виконуючи операції над сусідньою матрицею, ми можемо отримати важливе уявлення про природу графіка та взаємозв'язок між його вершинами.
Мінуси матриці суміжності
VxVНеобхідний простір матриці суміжності робить бори пам'яті. Графіки в дикій природі, як правило, не мають занадто багато зв’язків, і це є основною причиною, чому списки суміжностей є кращим вибором для більшості завдань.
Хоча основні операції прості, операції подобаються inEdgesі outEdgesє дорогими при використанні представлення матриці суміжності.
Приклади Python, Java та C / C ++
Якщо ви знаєте, як створити двовимірні масиви, ви також знаєте, як створити матрицю суміжності.
Python Java C C + # Adjacency Matrix representation in Python class Graph(object): # Initialize the matrix def __init__(self, size): self.adjMatrix = () for i in range(size): self.adjMatrix.append((0 for i in range(size))) self.size = size # Add edges def add_edge(self, v1, v2): if v1 == v2: print("Same vertex %d and %d" % (v1, v2)) self.adjMatrix(v1)(v2) = 1 self.adjMatrix(v2)(v1) = 1 # Remove edges def remove_edge(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 __len__(self): return self.size # Print the matrix def print_matrix(self): for row in self.adjMatrix: for val in row: print('(:4)'.format(val)), print def main(): g = Graph(5) g.add_edge(0, 1) g.add_edge(0, 2) g.add_edge(1, 2) g.add_edge(2, 0) g.add_edge(2, 3) g.print_matrix() if __name__ == '__main__': main()
// Adjacency Matrix representation in Java public class Graph ( private boolean adjMatrix()(); private int numVertices; // Initialize the matrix public Graph(int numVertices) ( this.numVertices = numVertices; adjMatrix = new boolean(numVertices)(numVertices); ) // Add edges public void addEdge(int i, int j) ( adjMatrix(i)(j) = true; adjMatrix(j)(i) = true; ) // Remove edges public void removeEdge(int i, int j) ( adjMatrix(i)(j) = false; adjMatrix(j)(i) = false; ) // Print the matrix 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(""); ) 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()); ) )
// Adjacency Matrix representation in C #include #define V 4 // Initialize the matrix to zero void init(int arr()(V)) ( int i, j; for (i = 0; i < V; i++) for (j = 0; j < V; j++) arr(i)(j) = 0; ) // Add edges void addEdge(int arr()(V), int i, int j) ( arr(i)(j) = 1; arr(j)(i) = 1; ) // Print the matrix void printAdjMatrix(int arr()(V)) ( int i, j; for (i = 0; i < V; i++) ( printf("%d: ", i); for (j = 0; j < V; j++) ( printf("%d ", arr(i)(j)); ) printf(""); ) ) int main() ( int adjMatrix(V)(V); init(adjMatrix); addEdge(adjMatrix, 0, 1); addEdge(adjMatrix, 0, 2); addEdge(adjMatrix, 1, 2); addEdge(adjMatrix, 2, 0); addEdge(adjMatrix, 2, 3); printAdjMatrix(adjMatrix); return 0; )
// Adjacency Matrix representation in C++ #include using namespace std; class Graph ( private: bool** adjMatrix; int numVertices; public: // Initialize the matrix to zero 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; ) ) // Add edges void addEdge(int i, int j) ( adjMatrix(i)(j) = true; adjMatrix(j)(i) = true; ) // Remove edges void removeEdge(int i, int j) ( adjMatrix(i)(j) = false; adjMatrix(j)(i) = false; ) // Print the martix void toString() ( for (int i = 0; i < numVertices; i++) ( cout << i << " : "; for (int j = 0; j < numVertices; j++) cout << adjMatrix(i)(j) << " "; cout << ""; ) ) ~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(); )
Додатки матриці суміжності
- Створення таблиці маршрутизації в мережах
- Навігаційні завдання
