最小生成树算法分析报告.doc

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