文章目錄

• • • • • 鄰接矩陣表示法
        • 鄰接矩陣示例
        • 鄰接矩陣的優(yōu)點
        • 鄰接矩陣的缺點
        • C示例
        • 鄰接矩陣應用
        • 參考文檔

????在本教程中，您將學習什么是鄰接矩陣。此外，您還將在C中找到鄰接矩陣的示例。
????鄰接矩陣是將圖G={V，E}表示為布爾矩陣的一種方法。

鄰接矩陣表示法

????矩陣的大小是 VxV，其中 V 是圖的頂點數(shù)，根據頂點 i 到頂點 j 是否有邊，條目 Aij 的值為1或0。

鄰接矩陣示例

????下圖顯示了一個圖形及其等效的鄰接矩陣。

????對于無向圖，由于每一條邊（i，j）的存在，矩陣關于對角線對稱，因此也有一條邊（j，i）。

鄰接矩陣的優(yōu)點

????添加邊、刪除邊以及檢查從頂點 i 到頂點 j 是否有邊等基本操作都是非常省時的常規(guī)操作。
????如果圖是密集的，且邊的數(shù)目較大，則鄰接矩陣是首選。即使圖和鄰接矩陣是稀疏的，我們也可以用稀疏矩陣的數(shù)據結構來表示它。
????圖的最大的優(yōu)勢來自于矩陣的使用。硬件的最新發(fā)展使我們能夠在GPU上執(zhí)行代價很大的矩陣運算。
????通過對鄰接矩陣進行運算，我們可以深入了解圖的性質及其頂點之間的關系。

鄰接矩陣的缺點

????鄰接矩陣的 VxV 空間要求使它占用很多內存。自然的圖通常沒有太多連接，這就是為什么鄰接列表是大多數(shù)任務的更好選擇的主要原因。
????雖然基本操作很簡單，但在使用鄰接矩陣表示時，像增加邊和刪除邊這樣的操作代價很大。

C示例

????如果您知道如何創(chuàng)建二維數(shù)組，那么您也知道如何創(chuàng)建鄰接矩陣。

// Adjacency Matrix representation in C#include <stdio.h> #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("\n");} }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; }

鄰接矩陣應用

• 在網絡中創(chuàng)建路由表
• 導航任務

參考文檔

[1]Parewa Labs Pvt. Ltd.Adjacency Matrix[EB/OL].https://www.programiz.com/dsa/graph-adjacency-matrix,2020-01-01.

總結

以上是生活随笔為你收集整理的了解邻接矩阵的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。