用邻接矩阵存储有 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)

sky33

难道不需要先在一维数组里面找到结点i，j 的序号，在跳到二维数组里面找 aij ？

发表于 2019-08-12 17:50:53 回复(2)

时光格

查二维数组的某个元素值，时间复杂度是O（1）

发表于 2019-07-02 09:51:01 回复(0)

在打卡的小飞象很想去毕业旅行

矩阵而不是链表，凎

发表于 2023-03-25 01:03:19 回复(0)

牛客702054823号

我觉得是o(1)吧，既然已经有了邻接矩阵的话，直接在邻接矩阵里搜索不就行了？

就是判断A[i][j]==or!=1?

发表于 2019-04-18 15:41:18 回复(0)

学术废物

当成两个节点分别结果是两个节点之间读题不认真

发表于 2022-03-11 22:22:39 回复(0)

妮妮妹妹

//用一个顺序表来存储顶点信息
int i，j，k，w;
scanf("%d%d"，&G->n，&G->e); //输入顶点数和边数
for(i = 0;i < G->n;i++) //读入顶点信息，建立顶点表
{
    G->vexs[i]=getchar();
}
for(i = 0;i < G->n;i++)
{
    for(j = 0;j < G->n;j++)
    {
        G->edges[i][j] = 0; //邻接矩阵初始化
    }
}
for(k = 0;k < G->e;k++)
{//读入e条边，建立邻接矩阵
    scanf("%d%d%d"，&i，&j，&w); //输入边(v i ,v j )上的权w
    G->edges[i][j]=w;
}
}//CreateMGraph

发表于 2021-06-09 10:22:28 回复(0)