数据结构课件第6章图.ppt

6.1 图的基本定义 6.2 图的表示 6.2.2 邻接表 6.2.3 邻接多表 6.3 连通图的遍历 6.3.1 深度优先搜索 6.3.2 广度优先搜索 6.3.3 生成树 6.4 图的连通性 6.5 最小代价生成树 6.5.1 克鲁斯卡尔算法 6.6 最短路径和传递闭包 6.6.2 所有顶点对之间的最短路径 所有顶点对之间的最短路径 算法思想逐个顶点试探法 求最短路径步骤: 初始时设置一个n阶