对有n个结点、e条边且采用数组表示法(即邻接矩阵存储)的无向图进行深度优先遍历，时间复杂度为______。

admin2019-10-08 31

问题对有n个结点、e条边且采用数组表示法(即邻接矩阵存储)的无向图进行深度优先遍历，时间复杂度为______。

选项 A、O(n²)
B、O(e²)
C、O(n+e)
D、O(n^*e)

答案A

解析图的邻接矩阵是指用一个矩阵来表示图中顶点之间的关系。对有n个结点的图，其邻接矩阵是一个n阶方阵。对于无向图来说，其邻接矩阵如下图所示：

当采用深度优先进行遍历的时候，查找所有邻接点所需要的时间是O(n²)。

转载请注明原文地址:https://kaotiyun.com/show/hUCZ777K

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

阅读以下说明，回答问题1～5，将解答填入对应的解答栏内。[说明]编写一个函数根据用户输入的偶对(以输入。表示结束)建立其有向图的邻接表。一个图的邻接表存储结构定义如下：#include＜stdio.h＞#defineMAX
阅读以下预备知识、函数说明和C代码，将应填入(n)处的字句写在对应栏内。[预备知识]①对给定的字符集合及相应的权值，采用哈夫曼算法构造最优二叉树，并用结构数组存储最优二叉树。例如，给定字符集合{a，b，c，d}及其权值2、7、4、5，可构造如图
阅读以下说明和流程图，从供选择的答案中选出应填入流程图(n)处的字句写在对应栏内。[说明]以下是某图像二元树存储与还原算法的主要思想描述。设一幅2n×2n的二值图像，以：“1”表示黑像素点，以“0”表示白像素点。图像二元树结构表示
阅读下列C++程序和程序说明，将应填入(n)处的字句写在对应栏内。【说明】设单链表的结点类和链表类的定义如下，链表不带有表头结点。请填空：#include＜iostream．h＞#include＜assert．h＞templ
Networks　can　be　interconnected　by　different　devices.　In　the　physical　layer,　networks　can　be　connected　by(66)or　hubs,　which　just　
In　the　open　systems　interconnection(OSI)reference　model,　"layer"　means　one　of　seven　conceptually　complete,(71)arranged　groups
The　program　memory　serves　basically　as　a　place(66)instructions,　the　coded　pieces　of　data(67)direct　the　activities　of　the　control
The　program　memory　serves　basically　as　a　place(66)instructions,　the　coded　pieces　of　data(67)direct　the　activities　of　the　control
The　program　memory　serves　basically　as　a　place(66)instructions,　the　coded　pieces　of　data(67)direct　the　activities　of　the　control

随机试题

Ithadover2,000apartmentcomplexes,agreatmarket,alargenumberofindustrialworkshops,anadministrativecenter,anumb
药物制剂的含量以
对杀伤病毒感染的靶细胞起主要作用的是
世界上最主要的畜产品期货交易中心是()。
婴幼儿时期脑的发育非常迅速，出生后的几年内，脑重量增加近4倍，()岁左右已基本接近成人。
温度计：气温
三个容积相同的瓶子里装满了酒精溶液，酒精与水的比分别是2：1，3：1，4：1。当把三瓶酒精溶液混合后，酒精与水的比是多少?
在几十位考古人员历经半年的挖掘下，规模宏大、内容丰富的泉州古城门遗址——德济门重现于世。考古人员再次发现一些古代寺院建筑构件。考古学家据此推测：元明时期该地附近曾有寺院存在。下列哪项如果为真，最能质疑上述推测?
法人的法定代表人越权订立合同的效力是()。
求曲线y=∫0xf(t)dt与y=2x—1交点的个数．其中f(x)在[0，1]上连续，f(x)＜1．

最新回复(0)

对有n个结点、e条边且采用数组表示法(即邻接矩阵存储)的无向图进行深度优先遍历，时间复杂度为______。

软件设计师上午基础知识考试

软考中级

阅读以下说明，回答问题1～5，将解答填入对应的解答栏内。[说明]编写一个函数根据用户输入的偶对(以输入。表示结束)建立其有向图的邻接表。一个图的邻接表存储结构定义如下：#include＜stdio.h＞#defineMAX

阅读下列C++程序和程序说明，将应填入(n)处的字句写在对应栏内。【说明】设单链表的结点类和链表类的定义如下，链表不带有表头结点。请填空：#include＜iostream．h＞#include＜assert．h＞templ

Networks can be interconnected by different devices. In the physical layer, networks can be connected by(66)or hubs, which just

In the open systems interconnection(OSI)reference model, "layer" means one of seven conceptually complete,(71)arranged groups

The program memory serves basically as a place(66)instructions, the coded pieces of data(67)direct the activities of the control

The program memory serves basically as a place(66)instructions, the coded pieces of data(67)direct the activities of the control

The program memory serves basically as a place(66)instructions, the coded pieces of data(67)direct the activities of the control

Ithadover2,000apartmentcomplexes,agreatmarket,alargenumberofindustrialworkshops,anadministrativecenter,anumb

药物制剂的含量以

对杀伤病毒感染的靶细胞起主要作用的是

世界上最主要的畜产品期货交易中心是()。

婴幼儿时期脑的发育非常迅速，出生后的几年内，脑重量增加近4倍，()岁左右已基本接近成人。

温度计：气温

三个容积相同的瓶子里装满了酒精溶液，酒精与水的比分别是2：1，3：1，4：1。当把三瓶酒精溶液混合后，酒精与水的比是多少?

法人的法定代表人越权订立合同的效力是()。

求曲线y=∫0xf(t)dt与y=2x—1交点的个数．其中f(x)在[0，1]上连续，f(x)＜1．

Networks　can　be　interconnected　by　different　devices.　In　the　physical　layer,　networks　can　be　connected　by(66)or　hubs,　which　just　

In　the　open　systems　interconnection(OSI)reference　model,　"layer"　means　one　of　seven　conceptually　complete,(71)arranged　groups

The　program　memory　serves　basically　as　a　place(66)instructions,　the　coded　pieces　of　data(67)direct　the　activities　of　the　control

The　program　memory　serves　basically　as　a　place(66)instructions,　the　coded　pieces　of　data(67)direct　the　activities　of　the　control

The　program　memory　serves　basically　as　a　place(66)instructions,　the　coded　pieces　of　data(67)direct　the　activities　of　the　control