Datastrucstures And Algorithms:Graphs 第七章图 1、 图的基本概念 图的存储表示 图的遍历与连通性 4、 最小生成树 5、最短路径 6、 活动网络 ALDS
1 物料管理 ALDS 1 DataStrucstures And Algorithms:Graphs 1、图的基本概念 2、图的存储表示 3、图的遍历与连通性 4、最小生成树 5、最短路径 6、活动网络 第七章 图
Datastrucstures And Algorithms:Graphs 图的基本概念 有向图G1 无向图G2 B ·结点或顶点： B ·结点或顶点： B ·有向边（弧）、弧尾或初始结 ·无向边或边 点、弧头或终止结点 A B ·有向图：G1=(V1,A1}) ·无向图：G2=(V2,{A2) V1=(A,B,C,D) V2=(A,B,C,D,E} A1={A,B>,<A,C>, A2={A,B),(A,C>,(B,D), <C,D>,<D,A>} (B,E>,(C,E),(D,E)} 2 ALDS
2 物料管理 ALDS 2 DataStrucstures And Algorithms:Graphs 图的基本概念 A B C D A B C D E 有向图 G1 无向图 G2 • 结点或 顶点： • 有向边（弧）、弧尾或初始结 点、弧头或终止结点 A B A B • 有向图：G1 =（V1，{A1}） V1 = {A,B,C,D} A1 = {<A,B>, <A,C>, <C,D>, <D,A>} • 结点或 顶点： • 无向边或边 A B • 无向图：G2 =（V2，{A2}） V2 = {A,B,C,D,E} A2 = {(A,B), (A,C>,(B,D), (B,E>, (C,E),(D,E)} A B
Datastrucstures And Algorithms:Graphs 图的基本概念 有向图G1 有向图G1的子图 A B A A B A B D C D D 无向图G2 无向图G2的子图 A B B E E E D 3 ALDS
3 物料管理 ALDS 3 DataStrucstures And Algorithms:Graphs 图的基本概念 A B C D 无向图 G2 A B C D A C A B C D 有向图G1的子图 A B C D E A B D E A A B C D A B C D E 无向图G2的子图 有向图 G1
Datastrucstures And Algorithms:Graphs 图的基本概念 无向图的连通性 ·路径：在无向图G=(N,{E)中由顶点v至v’的顶点序列。 回路或环：第一个顶点和最后一个顶点相同的路径。 ·简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。 连通：顶点v至v’之间有路径存在 连通图：无向图图G的任意两点之间都是连通的，则称G是连通图。 连通分量：极大连通子图 无向图G 无向图G的三个连通分量 M 4 ALDS
4 物料管理 ALDS 4 DataStrucstures And Algorithms:Graphs 图的基本概念 无向图的连通性 A B C D E •路径：在无向图G=(V,{E})中由顶点v至v‘’ 的顶点序列。 •回路或环：第一个顶点和最后一个顶点相同的路径。 •简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。 •连通：顶点v至v‘’ 之间有路径存在 •连通图：无向图图 G 的任意两点之间都是连通的，则称 G 是连通图。 •连通分量：极大连通子图 F G I J L H M K A B C D E H M F G I J K L 无向图G 无向图G的三个连通分量
Datastrucstures And Algorithms:Graphs 图的基本概念 有向图的连通性 路径：在有向图G=(八，{E》中由顶点V经有向边至v’的顶点序列。 回路或环：第一个顶点和最后一个顶点相同的路径。 ·简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。 连通：顶点v至v’之间有路径存在 ·强连通图：有向图图G的任意两点之间都是连通的，则称G是强连通图。 •强连通分量：极大连通子图 有向图G 有向图G的两个强连通分量 A B A B C D D 5 ALDS
5 物料管理 ALDS 5 DataStrucstures And Algorithms:Graphs 图的基本概念 有向图的连通性 •路径：在有向图G=(V,{E})中由顶点v经有向边至v‘’ 的顶点序列。 •回路或环：第一个顶点和最后一个顶点相同的路径。 •简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。 •连通：顶点v至v‘’ 之间有路径存在 •强连通图：有向图图 G 的任意两点之间都是连通的，则称 G 是强连通图。 •强连通分量：极大连通子图 有向图G 有向图G的两个强连通分量 A B C D A B C D