生成树 包含无向图G所有顶点的的极小连通子图称为G的生成树 极小连通子图意思是:该子图是G的连通子图,在该子图中删除任何 条边,子图不再连通, 若T是G的生成树当且仅当T满足如下条件 T是G的连通子图 T包含G的所有顶点 T中无回路 V2 2) V3 v4) V3(V4 Va 连通图G1 G1的生成树
生成树 包含无向图G 所有顶点的的极小连通子图称为G 的生成树 极小连通子图意思是：该子图是G 的连通子图，在该子图中删除任何一 条边，子图不再连通， 若T是G 的生成树当且仅当T 满足如下条件 T是G 的连通子图 T包含G 的所有顶点 T中无回路 连通图 G1 G1的生成树 V0 V3 V4 V1 V2 V0 V3 V4 V1 V2 V0 V4 V3 V1 V2
边的权:在图的边或弧上表示数字,表示与该边 相关的数据信息,这个数据信息就称该边的权( weight)。 网( network):边(或弧)上带权的图称为网。 VO 8 2 V2 3 5 V3 V4
边的权：在图的边或弧上表示数字，表示与该边 相关的数据信息，这个数据信息就称该边的权（ weight）。 网（network）：边（或弧）上带权的图称为网。 V0 V3 V4 V1 V2 8 2 4 6 5 3
7.2图的存储表示
7.2图的存储表示
0∞c V2 V3(V4 图的存储结构要保存两类信息: 1)顶点的数据 VOV1V2V3V4 2)顶点间的关系 邻接矩阵表示法 邻接表表示法
图的存储结构要保存两类信息： 1)顶点的数据 2)顶点间的关系 V0 V3 V4 V1 V2 V0 V1 V2 V3 邻接矩阵表示法 邻接表表示法 V0 V1 V2 V3 V4