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

admin2019-10-08 28

问题对有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
阅读以下说明和流程图，从供选择的答案中选出应填入流程图(n)处的字句写在对应栏内。[说明]以下是某图像二元树存储与还原算法的主要思想描述。设一幅2n×2n的二值图像，以：“1”表示黑像素点，以“0”表示白像素点。图像二元树结构表示
阅读下列C++程序和程序说明，将应填入(n)处的字句写在对应栏内。【说明】设单链表的结点类和链表类的定义如下，链表不带有表头结点。请填空：#include＜iostream．h＞#include＜assert．h＞templ
In　the　open　systems　interconnection(OSI)reference　model,　"layer"　means　one　of　seven　conceptually　complete,(71)arranged　groups
In　the　open　systems　interconnection(OSI)reference　model,　"layer"　means　one　of　seven　conceptually　complete,(71)arranged　groups
The　notion　of　NP-completeness　has　provided　a(66)mathematical　definition　for(67)intractability　of　NP　problems.　But　this　measure　a
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

随机试题

根据《流动资金贷款管理暂行办法》，单笔超过500万元的流动资金贷款资金支付，应采取贷款人受托支付方式。()
某人月初用一笔人民币投资股票，由于行情较好，他的资金每月都增加。即使他每月末都取出1000元用于日常开销，他的资金仍然在3个月后增长了一倍。问他开始时投资了多少人民币?
在真核细胞有氧呼吸过程中，O2参与形成()。
原告张某与邻居李某共同外出经商，二人因利润分配发生争执。某日李某到原告家索要，与原告发生争执，并发生厮打，后原告将李某打伤。事后，原告所在乡派出所几次找到原告要求其承担李某医药费，原告拒付。据此，原告所在地的市劳动教养工作领导小组，对原告作出劳动教养2年的
以下关于经济结构战略性调整的说法错误的是()。
以下不能输出字符A的语句是(注：字符A的ASCII码值为65，字符a的ASCII码值为97)
能够实现从指定记录集里检索特定字段值的函数是。
AccordingtoRyle,thetaskofphilosophyistorestate"______misleadingexpressions"informsthatarelogicallymoreaccura
Inwhatnowseemsliketheprehistorictimesofcomputerhistory,theearlypost-warera(战后时期),therewasaquitewidespreadcon
WhatwastheestimatednumberofdeathinMalawilastyear?

最新回复(0)

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

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

软考中级

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

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

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

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

The notion of NP-completeness has provided a(66)mathematical definition for(67)intractability of NP problems. But this measure a

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

根据《流动资金贷款管理暂行办法》，单笔超过500万元的流动资金贷款资金支付，应采取贷款人受托支付方式。()

某人月初用一笔人民币投资股票，由于行情较好，他的资金每月都增加。即使他每月末都取出1000元用于日常开销，他的资金仍然在3个月后增长了一倍。问他开始时投资了多少人民币?

在真核细胞有氧呼吸过程中，O2参与形成()。

以下关于经济结构战略性调整的说法错误的是()。

以下不能输出字符A的语句是(注：字符A的ASCII码值为65，字符a的ASCII码值为97)

能够实现从指定记录集里检索特定字段值的函数是。

AccordingtoRyle,thetaskofphilosophyistorestate"______misleadingexpressions"informsthatarelogicallymoreaccura

Inwhatnowseemsliketheprehistorictimesofcomputerhistory,theearlypost-warera(战后时期),therewasaquitewidespreadcon

WhatwastheestimatednumberofdeathinMalawilastyear?

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

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

The　notion　of　NP-completeness　has　provided　a(66)mathematical　definition　for(67)intractability　of　NP　problems.　But　this　measure　a

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