选项A错误，BFS和DFS时间复杂度并非始终相同，虽然都访问所有顶点和边，但由于其遍历方式不同，影响了实际复杂度。选项B错误，使用邻接矩阵时，BFS和DFS的时间复杂度都为O(n^2)，只是访问方式不同，不能说是时间复杂度不同。选项C错误，BFS和DFS的时间复杂度都与搜索路径无关，只与存储结构有关。选项D正确，BFS和DFS时间复杂度都只与存储结构有关，与具体的搜索路径无关。当使用邻接表时，两者时间复杂度均为O(n+e)；当使用邻接矩阵时，两者时间复杂度均为O(n^2)。