本题考察图的生成树概念。选项A错误，因为无论是深度优先生成树还是广度优先生成树，它们的边数都是n-1，n为图中顶点数。选项B正确，生成树是包含图中所有顶点的极小连通子图。选项C错误，因为生成树（无论是深度优先还是广度优先）都不是唯一的，存在多种可能的生成树。选项D错误，深度优先和广度优先搜索的时间复杂度都是O(V+E)，但它们在实际搜索过程中可能会有不同的表现。因此，正确答案是B。