06-6.2.1 邻接矩阵法

本文主要是介绍06-6.2.1 邻接矩阵法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

👋 Hi, I’m @Beast Cheng
👀 I’m interested in photography, hiking, landscape…
🌱 I’m currently learning python, javascript, kotlin…
📫 How to reach me --> 458290771@qq.com

---

喜欢《数据结构》部分笔记的小伙伴可以订阅专栏，今后还会不断更新。🧑‍💻
感兴趣的小伙伴可以点一下订阅、收藏、关注！🚀
谢谢大家！🙏

#define MaxVertexNum 100  // 顶点数目的最大值
typedef struct{char Vex[MaxVertexNum];  // 顶点表int Edge[MaxVertexNum][MaxVertexNum];  // 邻接矩阵，边表int vexnum, arcnum;  // 图的当前顶点数和边数/弧数
}MGraph;

如何求顶点的度、出度、入度？

无向图

第 i 个结点的度 = 第 i 行（或第 i 列）的非零元素个数

有向图

第 i 个结点的 出度 = 第 i 行 的非零元素个数
第 i 个结点的 入度 = 第 i 列的非零元素个数
第 i 个结点的度 = 第 i 行、第 i 列的非零元素个数 之和

邻接矩阵法存储带权图（网）

#define MaxVertexNum 100  // 顶点数目的最大值
#define INFINITY 最大的int值  // 宏定义常量“无穷”
typedef char VertexType;  // 顶点的数据类型
typedef int EdgeType;  // 带权图中边上权值的数据类型
typedef struct{VertexType [MaxVertexNum];  // 顶点EdgeType Edge[MaxVertexNum][MaxVertexNum];  // 边的权int vexnum, arcnum;  // 图的当前顶点数和边数/弧数
}MGraph;

邻接矩阵的性能分析

空间复杂度：$O(|V{|}^2)$ —— 只和顶点数有关，和实际的边数无关
适合用于存储 稠密图

邻接矩阵法的性质

设图 G 的邻接矩阵为 $A$ （矩阵元素为 0/1），则 $A^n$ 的元素 $A^n[i][j]$ 等于 由顶点 i 到顶点 j 的长度为 n 的路径的数目

这篇关于06-6.2.1 邻接矩阵法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---