圖的存儲結構：鄰接矩陣法

• 鄰接矩陣法：
• • 鄰接矩陣的定義：
  • 鄰接矩陣存儲無向圖：
  • 鄰接矩陣存儲有向圖：
  • 鄰接矩陣存儲網：
• 鄰接矩陣法的性質：
• 鄰接矩陣法的代碼實現：
• 矩陣運算A的n次冪的含義：
• 性能分析：

鄰接矩陣法：

鄰接矩陣的定義：

注： 其實就是一個二維數組，用二維數組的值表示這倆個節點是否存在邊

鄰接矩陣存儲無向圖：

ps： 無向圖的矩陣必定為對稱矩陣，所以可以壓縮成上三角存儲

鄰接矩陣存儲有向圖：

鄰接矩陣存儲網：

ps： 其實和存儲圖類似，只不過把要存儲的值換成了邊的權重

例：

PS: 無窮的表示：#define INFINITY //int的最大值

鄰接矩陣法的性質：

行： 在有向圖中，一個節點到另一節點的入度
列： 在有向圖中，一個節點到另一節點的出度

鄰接矩陣法的代碼實現：

//空間復雜度O(n2) #define MaxVertexTypeNum 100 typedef char VertexType; //頂點的類型 typedef int EdgeType; //邊的類型 typedef struct{VertexType Vex[MaxVertexTypeNum]; //存放頂點的一維數組 EdgeType Edge[MaxVertexTypeNum][MaxVertexTypeNum]; //存放邊的二維數組 int vexnum,arcnum; //頂點個數 }MGraph;

矩陣運算A的n次冪的含義：

例：
第一個11表示從B到E的一條路徑
第二個11表示從B到E的另一條路徑

結論： An[i][j] 表示從頂點Vi到頂點Vj長度為n的路徑的條數

性能分析：

空間復雜度：O(|v|^2)

總結

以上是生活随笔為你收集整理的数据结构之图的存储结构：邻接矩阵法的全部內容，希望文章能夠幫你解決所遇到的問題。

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