Algorithms and Datastrucstures Graphs 图的定义和术语 生成树:极小连通子图。包含图的所有n个结点,但只含图的n-1条边。在生成树中添 加一条边之后,必定会形成回路或环。 无向图G 无向图G的生成树 ALDS
6 物料管理 ALDS 6 Algorithms and DataStrucstures:Graphs 图的定义和术语 •生成树：极小连通子图。包含图的所有 n 个结点，但只含图的 n-1 条边。在生成树中添 加一条边之后，必定会形成回路或环。 A B C D E H M A B C D E H M 无向图G 无向图G的生成树
Algorithms and Datastrucstures: Graphs 图的定义和术语 完全图:有n(n-1)2条边的无向图。其中n是结点个数 的有向光全国:有m单条边的有向图,其中n是结点个数 边的权值,边有权的图称之为网络 其它术 ·邻接点: 无向图结点的度 语·有向图结点的出度和入度 无向图G1 有向图G2 ALDS
7 物料管理 ALDS 7 Algorithms and DataStrucstures:Graphs 图的定义和术语 •完 全 图：有 n(n-1)/2 条边的无向图。其中 n 是结点个数。 •有向完全图：有 n(n-1) 条边的有向图。其中 n 是结点个数。 •边的权值，边有权的图称之为网络。 •邻接点： •无向图结点的度 •有向图结点的出度和入度 A B C D E H M 无向图G1 图 的 其 它 术 语 有向图G2 A B C D
Algorithms and Datastrucstures: Graphs 图的存储结构 图的四种常用的存储形式 邻接矩阵和加权邻接矩阵( labeled adjacency matriⅸx) 邻接表 十字链表 邻接多重表 1、邻接矩阵和加权邻接矩阵( labeled adjacency matrⅸ) 无权值的有向图的邻接矩阵 设有向图具有n个结点,则用n行n列的布尔矩阵A表示该有向图 并且A[=1,如果i至j有一条有向边;A[=0如果i至j没有一条有向边 注意:A[=0。出度之和。入度:例列之和。 A 表示成右图矩阵 0000 000 ALDS
8 物料管理 ALDS 8 Algorithms and DataStrucstures:Graphs 图的存储结构 图的四种常用的存储形式： •邻接矩阵和加权邻接矩阵（labeled adjacency matrix） •邻接表 •十字链表 •邻接多重表 1、邻接矩阵和加权邻接矩阵（labeled adjacency matrix） A B C D •无权值的有向图的邻接矩阵 设有向图具有 n 个结点，则用 n 行 n 列的布尔矩阵 A 表示该有向图； 并且 A[i,j] = 1 , 如果i 至 j 有一条有向边；A[I,j] = 0如果 i 至 j 没有一条有向边 注意： A[i,i] = 0。出度: i行之和。入度: j列之和。 表示成右图矩阵 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0
Algorithms and Datastrucstures: Graphs 图的存储结构 1、邻接矩阵和加权邻接矩阵( labeled adjacency matrⅸκ)(续) 无权值的无向图的邻接矩阵 设无向图具有n个结点,则用n行n列的布尔矩阵A表示该无向图; 并且A[=1,如果i至j有一条无向边;A=0如果i至j没有一条无向边 注意:A[=0。i点的度:或例之和。上三角矩阵或下三角矩阵。 01100 1001 表示成右图矩阵 10001 01001 ALDS
9 物料管理 ALDS 9 Algorithms and DataStrucstures:Graphs 图的存储结构 1、邻接矩阵和加权邻接矩阵（labeled adjacency matrix）（续） •无权值的无向图的邻接矩阵 设无向图具有 n 个结点，则用 n 行 n 列的布尔矩阵 A 表示该无向图； 并且 A[i,j] = 1 , 如果i 至 j 有一条无向边；A[I,j] = 0如果 i 至 j 没有一条无向边 注意： A[i,i] = 0。i结点的度: i行或i列之和。上三角矩阵或下三角矩阵。 表示成右图矩阵 0 1 1 0 0 1 0 0 1 1 1 0 0 0 1 0 1 0 0 1 0 1 1 1 0 A B C D E
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 时间,太长。 ALDS
10 物料管理 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 ) 时间，太长