图的邻接表存储 数组实现

idx = 0
# 第idx条边的起点，w是终点，w是权重，first[i]=j:是第i顶点的最新加入的边的编号idx（j），pre[i]=j是第i条边的前一条边的是j，且i、j都是同一个顶点的边

if __name__ == '__main__':
    n, m = map(int, input().split(' '))

    # 这三个数组要比边数多一
    u = v = w = [-1] * (m + 1)
    print(id(u) == id(v))

    # first与per的大小要比顶点书大1
    pre = first = [-1 for i in range(0, n + 1)]

    # 第idx条边的起点，w是终点，w是权重，first[i]=j:是第i顶点的最新加入的边的编号idx（j），pre[i]=j是第i条边的前一条边的是j，且i、j都是同一个顶点的边
    # 读入边
    for i in range(1, int(m + 1)):
        temp = input().split(' ')
        u[i] = int(temp[0])

        v[i] = int(temp[1])
        w[i] = int(temp[2])
        print(u[i])
        pre[i] = first[u[i]]

        first[u[i]] = i

# 对每个顶点的指出边进行遍历
for i in range(1, n + 1):
    k = first[i]
    while (k != -1):
        print(f'{u[k]} -> {v[k]}:{w[k]}')
        k = next(k)

 输入：

1. 4 5
2. 1 4 9
3. 4 3 8
4. 1 2 5
5. 2 4 6
6. 1 3 7

输出：

Traceback (most recent call last):
  File "E:\Program\PYTHON\pythonProject3\main.py", line 23, in <module>
    pre[i] = first[u[i]]
IndexError: list index out of range

原因：

 u，v，w在地址中代表的同一列表

print(id(u) == id(v))

结构为True,所以在u[i],v[i],w[i]的值相同。导致pre[i] = first[u[i]]时越界

解决办法：

    u = [-1] * (m + 1)
    v = [-1] * (m + 1)
    w = [-1] * (m + 1)
    pre = [-1 for i in range(0, m + 1)]

    # first的大小要比顶点书大1
    first = [-1 for i in range(0, n + 1)]

完整代码:

if __name__ == '__main__':
    n, m = map(int, input().split(' '))
    # 这四个数组要比边数多一
    u = [-1] * (m + 1)
    v = [-1] * (m + 1)
    w = [-1] * (m + 1)
    pre = [-1 for i in range(0, m + 1)]

    # first的大小要比顶点书大1
    first = [-1 for i in range(0, n + 1)]
    # 第idx条边的起点，w是终点，w是权重，first[i]=j:是第i顶点的最新加入的边的编号idx（j），pre[i]=j是第i条边的前一条边的是j，且i、j都是同一个顶点的边

    # 读入边
    for i in range(1, int(m + 1)):
        temp = input().split(' ')
        u[i] = int(temp[0])
        v[i] = int(temp[1])
        w[i] = int(temp[2])
        pre[i] = first[u[i]]
        first[u[i]] = i

    # 对每个顶点的指出边进行遍历
    for i in range(1, n + 1):
        k = first[i]
        while (k != -1):
            print(f'{u[k]} -> {v[k]}:{w[k]}')
            k = pre[k]

思路来源：(58条消息) 图还可以这样存——邻接表的数组实现_不可数的爱的博客-CSDN博客

另一种实现方式：数组模拟邻接表 - AcWing