最小生成树算法及科学应用.ppt

最小生成树算法及应用 一生成树的概念 若图是连通的无向图或强连通的有向图则从图中任意一个顶点出发调用一次bfs或dfs后便可以系统地访问图中所有顶点若图是有根的有向图则从根出发通过调用一次dfs或bfs亦可系统地访问所有顶点在这种情况下图中所有顶点加上遍历过程中经过的边所构成的子图称为原图的生成树 对于不连通的无向图和不是强连通的有向图若有根或者从根外的任意顶点出发调用一次bfs或dfs后一般不能