作业帮OD矩阵和邻接矩阵是一回事么?
来源：学生作业帮助网 编辑：作业帮 时间：2024/11/08 19:31:16
OD矩阵和邻接矩阵是一回事么?
OD矩阵和邻接矩阵是一回事么?
OD矩阵和邻接矩阵是一回事么?
这是图论的知识,OD矩阵是图顶点的出度的矩阵 图的邻接矩阵如下介绍 1．图的邻接矩阵表示法 在图的邻接矩阵表示法中： ① 用邻接矩阵表示顶点间的相邻关系 ② 用一个顺序表来存储顶点信息 2．图的邻接矩阵(Adacency Matrix) 设G=(V,E)是具有n个顶点的图,则G的邻接矩阵是具有如下性质的n阶方阵： 【例】下图中无向图G 5 和有向图G 6 的邻接矩阵分别为A l 和A 2 . 从图的邻接矩阵表示法中可以得到如下结论： （1）对于n个顶点的无向图,有A（i,i）=0,1≤i≤n. （2）无向图的邻接矩阵是对称的,即A（i,j）=A（j,i）,1≤i≤n,1≤j≤n. （3）有向图的邻接矩阵不一定对称的.因此用邻接矩阵来表示一个具有n个顶点的有向图时需要n 2 个单位来存储邻接矩阵；对有n个顶点的无向图则需存入上（下）三角形,故只需n（n+1）/2个单位. （4）无向图的邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的度TD（v i ）. （5）有向图的邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的出度OD（v i ）[或入度ID（v i ）]. 3．网（带权值的图）的邻接矩阵 若G是网络,则邻接矩阵可定义为： 其中： w ij 表示边上的权值； ∞表示一个计算机允许的、大于所有边上权值的数. 【例】下面(a)是一个带权图,（b）是对应的邻接矩阵的存储结构 （a）带权图 （b）邻接矩阵 4．邻接矩阵的图类 const int MaxVertices=10; const int MaxWeight=32767; class AdjMWGraph { private: int Vertices[10]; //顶点信息的数组 int Edge[MaxVertices][MaxVertices]; //边的权值信息的矩阵 int numE; //当前的边数 int numV; //当前的顶点数 public: ………; //公有函数 private: ………; //私有函数 } 注意： ① 在简单应用中,可直接用二维数组作为图的邻接矩阵（顶点表及顶点数等均可省略）. ② 当邻接矩阵中的元素仅表示相应的边是否存在时,EdgeTyPe可定义为值为0和1的枚举类型. ③ 无向图的邻接矩阵是对称矩阵,对规模特大的邻接矩阵可压缩存储. ④ 邻接矩阵表示法的空间复杂度S(n)=0(n 2 ).