1．有向图的边也称为 弧 。 2．有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的 出度 。 3．图的逆邻接表存储结构只适用于 有向 图。 4．n个顶点的完全无向图有 n(n-1)/2 条边。 5．图常用的存储方式有邻接矩阵和 邻接表 等。 6．有n条边的无向图邻接矩阵中，1的个数有 2n 个。 7．图的邻接矩阵表示法是表示 顶点 之间相邻关系的矩阵。 8．n个顶点e条边的图若采用邻接矩阵存储，则空间复杂度为 O（n2） 。 9．n个顶点e条边的图若采用邻接表存储，则空间复杂度为 O（n+e） 。 10．设有一稀疏图G，则G采用 邻接表 存储比较节省空间。 11．设有一稠密图G，则G采用 邻接矩阵 存储比较节省空间。 12．对有n个顶点，e条弧的有向图，其邻接表表示中，需要 n+e 个结点。 13．无向图的邻接矩阵一定是 对称 矩阵。 14．有向图的邻接表表示适于求顶点的 出度 。 15．有向图的邻接矩阵表示中，第i列上非0元素的个数为顶点Vi的 入度 。 16．从图中某一顶点出发，访遍图中其余顶点，且使每一顶点仅被访问一次，称这一过程为图的 遍历 。 17．具有6个顶点的无向图至少应有 5 条边才能确保是一个连通图。 18．对于具有n个顶点的图，其生成树有且仅有 n-1 条边。 19．一个连通网的最小生成树是该图所有生成树中 权 最小的生成树。 20．若要求一个稠密图G的最小生成树，最好用 Prim 算法来求解。  |
|免责声明|本站介绍|工控课堂
( 沪ICP备14007696号-3 )|网站地图
GMT+8, 2019-4-23 20:53 , Processed in 0.043547 second(s), 34 queries .
Powered by Discuz! X3.4
© 2001-2017 Comsenz Inc.
