如果从一个顶点出发又回到该顶点,则此路径叫做()。
无向图中一个顶点的度是指图中( )。A.通过该顶点的简单路径数 B.通过该顶点的回路数 C.与该顶点相邻的顶点数 D.与该顶点连通的顶点数
点击查看答案
以下关于无向连通图 G 的叙述中,不正确的是(60)。A.G 中任意两个顶点之间均有边存在 B.G 中任意两个顶点之间存在路径 C.从 G 中任意顶点出发可遍历图中所有顶点 D.G 的临接矩阵是对称矩阵
阅读下列说明和?C?代码,回答问题?1?至问题?2,将解答写在答题纸的对应栏内。 【说明】 一个无向连通图?G?点上的哈密尔顿(Hamiltion)回路是指从图?G?上的某个顶点出发,经过图上所有其他顶点一次且仅一次,最后回到该顶点的路劲。一种求解无向图上哈密尔顿回 路算法的基础私下如下:假设图?G?存在一个从顶点?V0?出发的哈密尔顿回路?V1——V2——V3——...——Vn-1——V0。算法从顶点?V0?出发,访问该顶点的一个未被访问的邻接顶点?V1,接着从顶点?V1?出发,访问?V1?一个未被访问的邻接顶点?V2,..。;对顶点?Vi,重复进行以下操作:访问?Vi?的一个未被访问的邻接接点?Vi+1;若?Vi?的所有邻接顶点均已被访问,则返回到顶点?Vi-1,考虑Vi-1?的下一个未被访问的邻接顶点,仍记为?Vi;知道找到一条哈密尔顿回路或者找不到哈密尔顿回路,算法结束。 【C?代码】 下面是算法的?C?语言实现。 (1)常量和变量说明 n :图?G?中的顶点数 c[][]:图?G?的邻接矩阵 K:统计变量,当期已经访问的定点数为?k+1 x[k]:第?k?个访问的顶点编号,从?0?开始 Visited[x[k]]:第?k?个顶点的访问标志,0?表示未访问,1?表示已访问 ⑵C?程序【问题?1】(10?分) 根据题干说明。填充?C?代码中的空(1)~(5)。 【问题?2】(5?分) 根据题干说明和?C?代码,算法采用的设计策略为( ),该方法在遍历图的顶点时,采用的 是(?)方法(深度优先或广度优先)。
如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点,则该图一定是()。A一棵树B有回路C完全图D连通图
若从无向图中任意一个顶点出发进行1次深度优先搜索便可以访问到该图的所有顶点,则该图一定是一个()。A、非连通图B、强连通图C、连通图D、完全图
在带权图中,两个顶点之间的路径长度是()。A、路径上的顶点数目B、路径上的边的数目C、路径上顶点和边的数目D、路径上所有边上的权值之和
已知n个顶点的有向图,若该图是强连通的(从所有顶点都存在路径到达其他顶点),则该图中最少有多少条有向边()A、nB、n+1C、n-1D、n*(n-1)