如何做微商城网站,动漫设计培训班收费,一键生成广告,商城网站建设效果一.邻接矩阵法存储不带权图#xff1a;
结点不带权值#xff1a; 1.左图的无向图中#xff0c;A到B直达的有一条路#xff0c;所以A行B列的值为1#xff1b;
左图的无向图中#xff0c;A到F没有直达的路#xff0c;所以A行F列的值为0#xff1b;
结论#xff1a;无…一.邻接矩阵法存储不带权图
结点不带权值 1.左图的无向图中A到B直达的有一条路所以A行B列的值为1
左图的无向图中A到F没有直达的路所以A行F列的值为0
结论无向图中采用邻接矩阵法0表示两个顶点不邻接1表示两个顶点邻接边对应两个1
2.右图的有向图中A到B直达的有一条路所以A行B列的值为1
B到A没有直达的路所以B行A列的值为0
结论有向图中采用邻接矩阵法1表示有向边(弧)有向边(弧)对应一个1
3.上述图片中的代码顶点表是要存入边表的即表中存点
4.顶点表也可以是其他类型如整型自定义数据类型
5.int型表示边占4个字节(4B)或者8个字节(8B)用bool型或枚举型变量表示边则占1个字节(1B)
6.注表中的顶点是有下标(编号)的这样是为了在表中方便寻找两个顶点的关系如A的下标为0B的下标为1这样比如在左图的无向图中只需要找第0行第1列就可以查找顶点A和B的关系
7.如何求顶点的度(针对无向图和有向图)入度和出度(只针对有向图) 无向图如上述图片中的B结点在B结点这一行中有几个非0元素就有几个度显然A,E,F列为1即不为0因此B的度为3(看B结点这一列也可以结果一致)
结论第i个结点的度第i行(第i列)的非零元素个数时间复杂度为O(n)或者O(|v|)v是顶点数 有向图某个结点的出度的个数就是该结点所在行(不能是列)中非0元素的个数如A结点的出度为1 某个结点的入度的个数就是该结点所在列(不能是行)中非0元素的个数如A结点的入度为2 有向图中某个结点的度等于该结点入度的个数加出度的个数时间复杂度为O(n)或者O(|v|)v是顶点 数因此A结点的度为3 二.邻接矩阵法存储带权图(网) 1.带权图中存储的就是权值比如左图的无向图A直达B的权值为5那么A行B列的值为5
左图的无向图B直达C不存在权值即B直达不了C那么B行C列的值可以用无穷来表示
2.权值的类型可以是整型浮点型或者自定义数据类型等
3.有时也会把自己指向自己的权值设为0如A到A的权值为0
4.邻接矩阵法存储带权图(网)中结点到结点的权值如果为0或者是无穷那么表示与之对应的两个结点之间不存在边 三.邻接矩阵法的性能分析
1.如果图中有n个顶点(结点)那么存储该图的顶点就需要一个一维数组此时存储顶点的空间复杂度为O(n),
还需要定义一个n * n的二维数组来存储和这些顶点相关的边的信息所以存储边的空间复杂度为O(n * n)
所以总共空间复杂度为O(n)O(n * n)等价于O(n * n)
结论邻接矩阵法的空间复杂度为O(n * n)或O(|v| * |v|)v为顶点数--只和顶点数有关和实际的边数无关导致的弊端就是如果顶点很多但边比较少就会使得存储边的二维数组空间浪费因此邻接矩阵法适用于存储稠密图即边多的图 四.邻接矩阵法的性质讨论不带权值的图即矩阵元素只有01
0表示从一个顶点到另一个顶点没有路径1表示从一个顶点到另一个顶点有路径 A到B到D的长度为2符合要找的路径长度所以算了进去 注简单图中自己到自己的权值为0 上述图片中右下角的矩阵中的值表示的是顶点到顶点长度为2的路有几条如A行C列中顶点A到顶点C长度为2的路有1条 五.总结 邻接矩阵法的空间复杂度为O(n*n)n为顶点数由此可看出邻接矩阵法的空间复杂度较高不适合存储稀疏图如果使用邻接矩阵法存储稀疏图会造成大量的空间浪费。
