首页 > 试题广场 > 用邻接矩阵存储有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)

3个回答

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



编辑于 2019-04-19 14:09:53 回复(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)