🏷️ 知识点：时间复杂度

写出从图的邻接表表示转换成邻接矩阵表示的算法。

[tag_link]

参考答案

设图有 n 个顶点，邻接矩阵为 A。先将 A 的 n×n 元素初始化为 0；再依次扫描每个顶点 i 的边链表，对其中每条边 i→j 置 A[i][j]=1。若为无向图，边结点按邻接表约定会在两个端点链表中出现，仍按扫描结果赋值即可。

for i = 0..n-1:
    for j = 0..n-1:
        A[i][j] = 0
for i = 0..n-1:
    p = Adj[i].first
    while p != null:
        A[i][p.adjvex] = 1
        p = p.next

初始化矩阵需要 O(n²)，扫描顶点表和全部边表需要 O(n+e)（无向图的边表结点数为 2e，仍为 O(n+e)），所以严格总复杂度为 O(n²+n+e)=O(n²+e)，空间复杂度为 O(n²)。若题目约定矩阵已预先清零，则只计转换扫描部分，为 O(n+e)。

易错点

不能只遍历一个顶点的链表，也不能把无向图的两次边表出现误算成两条不同的边；初始化复杂度与填边扫描复杂度要分别说明。