Algorithms and Datastrucstures: Graphs 图的存储结构 1、邻接矩阵和加权邻接矩阵( labeled adjacency matrⅸκ)(续) 有向图的加权邻接矩阵 设有向图具有n个结点,则用n行n列的矩阵A表示该有向图; 并且A[=a,如果i至j有一条有向边且它的权值为a。A[i]=(空或其它标 志;如果i至j没有一条有向边。 a b 表示成右图矩阵 b 优点:判断任意两点之间是否有边方便,仅耗费o(1)时间。 缺点:即使<<n2条边,也需内存n2单元,太多;仅读入数据耗费o(n2) 10 时间,太长。 ALDS10 物料管理 ALDS 10 Algorithms and DataStrucstures:Graphs 图的存储结构 1、邻接矩阵和加权邻接矩阵（labeled adjacency matrix）（续） •有向图的加权邻接矩阵 设有向图具有 n 个结点，则用 n 行 n 列的矩阵 A 表示该有向图； 并且 A[i,j] = a , 如果i 至 j 有一条有向边且它的权值为a。A[i,j] = ‘空 或其它标 志；如果 i 至 j 没有一条有向边。 A B C D 表示成右图矩阵 a b b b a a a a b a b b 优点：判断任意两点之间是否有边方便，仅耗费 O(1) 时间。 缺点：即使 << n2 条边，也需内存 n2 单元，太多; 仅读入数据耗费 O( n2 ) 时间，太长