数据结构基础—图(上)

图的基本概念

最近因为各种考试(四级怕不是要明年再见了)消失了一段时间,也攒了一堆想要写的东西,不过后面几周还是有一轮接着一轮的考试,所以估计又要不定期鸽了。话说图这一章抄了别人的答案,结果选择题都没及格,唉,还是得自己老老实实做啊

1-1无向连通图至少有一个顶点的度为1。
想个特殊情况,只有一个顶点的图

1-2用邻接表法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关。
1-3用邻接矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关。
图的存储主要就是邻接表和邻接矩阵了,而前者因为要保存顶点和其边的信息所以空间应该为v+e,而后者则是利用矩阵来表示每两个顶点之间的关系所以只和顶点个数有关

1-4在一个有向图中,所有顶点的入度与出度之和等于所有边之和的2倍。
这个很好想吧,一个线有两个度,所以你计算的度要除于2

1-5在任一有向图中,所有顶点的入度之和等于所有顶点的出度之和。
有来有回,来而不往非礼也

1-6如果无向图G必须进行两次广度优先搜索才能访问其所有顶点,则G中一定有回路。
要是那样的话BFS岂不是太弱了,人家本来就是可以找到所有顶点的,这里应该是说明图不连通的……提一下BFS在无向图找回路的问题吧,其实很好想象,如果一个无向图他没有环的话不就是个树嘛,假设我们层序遍历时发现某个顶点竟然还有个边,那不就说明他有回路了嘛。

(1)通过广度遍历(BFS)访问图的所有点,对于每个点,都检测和已访问过的点是否有边(除了和它连接的上层节点)。
(1.1)如果有边,说明有回路(有环)。如果对于每个点,都没有和已访问过的点有边,说明从该点出发的当前图没有回路(无环)。
(2)如果从任意点开始的BFS,以上操作(1)均说明无回路,则没有回路。

1-7如果无向图G必须进行两次广度优先搜索才能访问其所有顶点,则G一定有2个连通分量。
这是对的,唯一可以让BFS断开的就是“没有桥的大陆”,而一个“大陆”就是一个连通分量

1-8无向连通图所有顶点的度之和为偶数。
上面提到了,一个边有两度,所以你的度的和肯定是整数倍啦

1-9无向连通图边数一定大于顶点个数减1。
顶点个数减1这个是不是很眼熟啊?这是树有n个结点的边数,那边没有方向的树是不是图啊?那肯定是啊

2-1若无向图G =(V,E)中含10个顶点,要保证图G在任何情况下都是连通的,则需要的边数最少是:
这题和上面的一样,既然是最少了那就考虑树的形状,n-1即可

2-2给定一个有向图的邻接表如下图,则该图有?个强连通分量。

首先把只有出度的点直接拿走就行了,因为你弄死它它也回不来
之后我们就以0作为开始,那么0可以找到5,5可以找到1,1有两个出度所以就要开始分类了
走0的话就可以回到之前走过的点了,所以这些点也就一定是一个连通分量里的了,这种情况over。
走3的话又可以走两个,再次分开
走的是0的话又回到了已经经过的点,所以他们是一个连通分量的,over(此时这组连通分量已经有了0,5,1,3)
走的是4的话到头了,所以4单独拿出来成一个连通分量。
剩下一个2没有被找到过,所以也是一个连通分量。

2-3给定有向图的邻接矩阵如下:

顶点2(编号从0开始)的出度和入度分别是:
横看成岭侧成峰,远近高低…呃,跑题了,这个就是横竖看的问题,因为是2所以我们锁定第三行的时候就是2“出去”的情况,而当我们锁定第三列的时候就是“进入”2的情况了

2-4下面给出的有向图中,有?个强连通分量。

答案为2 ({1,2,3,4}, {0})又是找强连通分量的题目,唉,真麻烦,思路还是刚才那样,不说了。

2-5下面给出的有向图中,各个顶点的入度和出度分别是(图片和上面的一一样):
这个查查就行了,不说了

2-6如果G是一个有36条边的非连通无向图,那么该图顶点个数最少为多少?
这个首先考虑一下无向图(先忽略非连通)的最大边数,每个点可以和他之外的所有顶点有边,所以就应该是n*(n-1)条边。令这个等于36,解得n等于9,又因为题目是非连通的,所以我们再加一个点,也就是10

2-7下面关于图的存储的叙述中,哪一个是正确的?
又是关于存储的问题,表是v+e,矩阵是n的平方,不说了

2-8关于图的邻接矩阵,下列哪个结论是正确的?
选项不想放出来,一句话就是无向图矩阵一定对称,有向图不一定对称

2-9设N个顶点E条边的图用邻接表存储,则求每个顶点入度的时间复杂度为:
看见这种题无脑选v+e就对了。。。。很好想,你在表里要先遍历v找到你要的点,然后在v的e域里再找各个边统计一遍,很显然是这个答案

2-10在一个无向图中,所有顶点的度数之和等于所有边数的多少倍?
2-11在一个有向图中,所有顶点的入度与出度之和等于所有边之和的多少倍?
一个边俩度,肯定是2倍

2-13设无向图的顶点个数为N,则该图最多有多少条边?
怎么老是这种问题。。。不写了

2-14下列关于无向连通图特征的叙述中,正确的是:
1 所有顶点的度之和为偶数
2 边数大于顶点个数减1
3 至少有一个顶点的度为1
很显然只有1是对的,其实2、3前面也都说过了,2是因为树也是无向连通图,3是特殊情况一个点的时候

2-15若无向图G =(V,E)中含7个顶点,要保证图G在任何情况下都是连通的,则需要的边数最少是:
这个题说实话有点心机boy了,注意它说的是任何情况,还得是最少边数,这咋办呐?其实很简单,任何情况就是说不管边怎么摆你都保证连通,那么为了应对某些熊(chu)孩(ti)子(ren)把所有的边都扔到一两个点这种情况,我们就得保证边的数量足够多。多是多少呢?n乘以n-1除以2?当然不是了,我们只需要“喂饱”前n-1个点就成你了,最后一个点一个边连起来就成了(因为前n个点都吃饱了不可能放得下了,只可能连到最后一个点),所以答案是6乘以5再除以2,最后加1.

2-16在N个顶点的无向图中,所有顶点的度之和不会超过顶点数的多少倍?
简单了,最多的是边的个数是n乘以n-1除以2,度是边的二倍,也就是n乘以n-1,也就是n-1倍啦

2-17对于一个具有N个顶点的无向图,要连通所有顶点至少需要多少条边
就是树呗,n-1就完事了

2-18具有N(N>0)个顶点的无向图至多有多少个连通分量?
N个呗,所有点都不连通的时候

2-19一个有N个顶点的强连通图至少有多少条边?
强连通也就是是有向图的连通,围个圈不就是最小情况了嘛。

2-20如果G是一个有28条边的非连通无向图,那么该图顶点个数最少为多少
这个眼熟啊,n乘以n-1 = 56呗,算出来是8,再加上个单独的不让它连通的点,也就是9

2-21对于有向图,其邻接矩阵表示比邻接表表示更易于:
唯一的好处就是求入度方便了,求别的都半斤八两

2-22对于一个具有N个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小是:
太简单了,n的方

2-23若一个有向图用邻接矩阵表示,则第i个结点的入度就是:
第i列的非零元素个数,入度看列,出度看行,over

2-24下列选项中,不是下图深度优先搜索序列的是:

这个太简单了,不说了

2-27已知无向图G含有16条边,其中度为4的顶点个数为3,度为3的顶点个数为4,其他顶点的度均小于3。图G所含的顶点个数至少是:

16条边也就是32个度,3x4,4x3一共是24度,还剩8度,因为都小于3,所以我们就认为都是2,也就是4个,加起来一共11个

2-29图的广度优先遍历类似于二叉树的:
广度层序,深度中序

2-33如果从无向图的任一顶点出发进行一次深度优先搜索可访问所有顶点,则该图一定是:
连通图呗,你只要连通这两种遍历方法都可以找到所有的顶点

其他的题目基本上就是以上题目的变形或者是无脑重复,不说了。

Successful