My first note was about efficiency of the implementation. When followlinks is 
true, you can avoid testing entry.is_link() and creating the symlinks set.

The new implementation of os.walk() changes a behavior. The problem is that a 
symlink to a directory can become a directory. It is documented that the 
caller can remove or add a directory to directory list and for sure this 
feature is used in third-party code. In my example a directory list is even 
not changed, but file system is changed.

I think that majority of uses of os.walk() will be not affected by this change, 
but for sure there is a code that will be broken and we can receive bug 
reports after releasing 3.6.

New behavior also is not consistent with os.fwalk().