【数据结构】图的定义、存储-Toy模板网

这篇具有很好参考价值的文章主要介绍了【数据结构】图的定义、存储。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

对王道数据结构选择题做错和不清楚的题的简单纠错

图的定义

一个有n个顶点和n条边的无向图一定是有环的

一个无向图有n个顶点和n-1条边，可以使它连通单没有环，若再加一条边，则会形成环
若图中顶点数为n，则它的生成树有n-1条边，去掉一条边变成非连通图；加上一条边变成一个回路（环）
2.（D）

对于n个顶点,e条边的无向图，所有顶点的度之和为2e，即无向图的全部顶点的度的和等于边数的两倍
【分析】设顶点有x个，则20+12+2(x-9)=46,x=16
3.

在n个顶点的有向图中，顶点的度最大可达2n-2

【分析】有向图中，顶点的度=出度+入度
在n个顶点的有向图中，任意一个顶点最多还可以和其他n-1个顶点有一对指向相反的边相连，则度数为2(n-1)
4.（D）

生成树是包含全部顶点的极小连通子图，且不是环
无向图中的极大连通子图称为连通分量
5.

若具有n个顶点的图是一个环，则它有n棵生成树

生成树加一条边就是环，环减一条边就是生成树，所以n个顶点的环有n条边，每条边都可以被减掉，共有n种减法，所以有n棵生成树
6.（C）

任何情况下，考虑最坏的情况，对于非连通图，最多可以有15条边，则要时连通图最少有16条边。
因为要满足的是任何条件，所以要考虑最坏的情况，而不是最好的情况下需要6条边

7.（B）（D）

有向图的入度是其第i列的非0元素之和，无向图的度是第i行或第i列的非0元素之和
8.

若邻接表中有奇数个边表结点，则图为有向图

无向图采用邻接表表示时，每条边存储两次，所以一定是偶数
不是无向图还能是什么图！！！是有向图
9.（C）

边表不包括顶点表，v在边表中出现的次数是v的入度
10.

【数据结构】图的定义、存储文章来源地址https://www.toymoban.com/news/detail-475184.html

到了这里，关于【数据结构】图的定义、存储的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！