试题详情
- 简答题具有n个顶点的强连通图至少有多少条边?这样的图应该是什么形状?
- 具有n个顶点的强连通图至少有n条边,这样的图是一个由n个顶点构成的环。
强连通图是相对于有向图而言的。由于强连通图要求图中任何两个顶点之间能够相互连通,因此每个顶点至少要有一条以该顶点为弧头的弧和一条以该顶点为弧尾的弧,每个顶点的入度和出度至少各为1,即顶点的度至少为2,这样根据图的顶点数、边数以及各项点的度三者之间的关系计算可得:边数=2×n/2=n。 关注下方微信公众号,在线模考后查看
热门试题
- 稀疏多项式采用的循环链表存储结构Link
- 已知一个图的邻接矩阵表示,删除所有从第一
- 数据结构里,下面关于字符数组描述正确的是
- 下面关于m阶B树说法正确的是() ①每个
- 在一棵度为M树中,度为1的结点数为N
- 排序
- 设一棵二叉树的先序序列:A B
- 设散列表容量为7(散列地址空间0..6)
- 若一个图中包含有k个连通分量,若要按照深
- 分析以下各程序段,并用大O记号表示其执行
- 数组名表示数组的首地址。
- 在散列查找中,平均查找长度主要与()有关
- 依次在初始为空的队列中插入元素a,b,c
- 已知如下所示长度为12的表:(Jan,
- 函数实现串的模式匹配算法,请在空格处将算
- 已知数据序列{10,18,4,3,6,1
- 设哈希函数H(key)=key MOD1
- 判定一个顺序栈S(栈空间大小为n)为空的
- 在一棵树中,()没有前驱结点。
- 分析下面语句段执行的时间复杂度。