首页 > 试题广场 > 用邻接矩阵存储有n个结点(0,1,...,n)和e条边的有向
[单选题]

用邻接矩阵存储有n个结点(0,1,...,n)和e条边的有向图(0≤e≤n(n-1))。判断结点i,j(0≤i,j≤n-1)有边的时间复杂度是()

  • O(1)
  • O(n)
  • O(e)
  • O(n+e)
推荐
选A。该题考察的是有向图抽象成一个二维数组矩阵,判断二维数组元素V[i,j]为1的复杂度,属于常数阶O(1)



编辑于 2019-04-19 14:09:53 回复(0)
难道不需要先在一维数组里面找到结点i,j 的序号,在跳到二维数组里面找 aij ?
发表于 2019-08-12 17:50:53 回复(0)
查二维数组的某个元素值,时间复杂度是O(1)
发表于 2019-07-02 09:51:01 回复(0)
邻接矩阵:A,A[0][1]=1,表示点0到点1有边;A[1][0]=0,表示点1到点0没有边,所以时间复杂度为O(1)

0 1 2
0 0 1 1
1 0 1 0
2 0 1 1

发表于 2019-04-18 16:36:54 回复(0)
我觉得是o(1)吧,既然已经有了邻接矩阵的话,直接在邻接矩阵里搜索不就行了?
就是判断A[i][j]==or!=1?
发表于 2019-04-18 15:41:18 回复(0)