如果按深度优先搜索算法从图中任意一点出发均可以访问图中所有的顶点,则该图一定是( )
A、
连通图
B、
有回路图
C、
完全图
D、
无环图
【正确答案】:A
【题目解析】:
连通图深度优先搜索的基本思想: 假定以图中某个顶点vi为出发点, 首先访问出发点vi,然后任选一个vi的未访问过的邻接点vj,以vj为新的出发点继续进行深度优先搜索, 依此类推, 直至图中所有顶点都被访问过。
A:如果图中的任意两个顶点vi和vj都是连通的,则称G为连通图。
B:第一个顶点和最后一个顶点相同的路径称为回路或环。
C:任何两点之间都有边的无向图称为无向完全图。任何两点之间都有弧的有向图称为有向完全图。
D:任何一个无环有向图,其全部顶点可以排成一个拓扑序列。
故本题选A。