题目内容
(请给出正确答案)
[主观题]
试写一算法,判断以邻接表方式存储的有向图中是否存在由顶点vi到顶点vi的路径(i≠j)。注意:算法中涉
试写一算法,判断以邻接表方式存储的有向图中是否存在由顶点vi到顶点vi的路径(i≠j)。注意:算法中涉及的图的基本操作必须在存储结构上实现。
答案
查看答案
试写一算法,判断以邻接表方式存储的有向图中是否存在由顶点vi到顶点vi的路径(i≠j)。注意:算法中涉及的图的基本操作必须在存储结构上实现。
第1题
已知一具有n个顶点的有向图G=(V,E)采用邻接表存储方法。请写一算法,检查任意给定序列v1,v2,v3,…,vn(vi∈V,1≤i≤n)是否为该有向图的一个拓扑序列。 若是,算法给出信息1;否则,给出信息0。
第2题
设无向图G有n个顶点e条边,写一算法建立G的邻接多重表,要求该算法时间复杂性为O(n+e),且除邻接多重表本身所占空间之外只用O(1)辅助空间。【东南大学1995六(16分)1997二(15分)】
第3题
设G是含有n个顶点(设顶点编号为1,2,…,n)的有向无环图。将G用如下定义的邻接表存储(编者略)。请编写一个非递归算法求G的每个顶点出发的最长路径的长度(每条弧的长度均为1)并存入mpl域中。要求:首先写出算法思想,然后写算法过程。
第4题
第9题
在图采用邻接表存储时,求最小生成树的Prim算法的时间复杂度为()。
A.O(n)
B.O(n+e)
C.O(n2)
D.O(n3)
第11题
采用邻接表存储的图的广度优先遍历算法类似于二叉树的()。
A.先序遍历
B.中序遍历
C.后序遍历
D.按层遍历