/goit-algo-hw-06

Primary LanguagePython

Результати пошуку шляху між містами Львів та Донецьк за допомогою DFS та BFS:

  • DFS шлях: ['Львів', 'Івано-Франківськ', 'Чернівці', 'Хмельницький', 'Рівне', 'Житомир', 'Київ', 'Черкаси', 'Кропивницький', 'Дніпро', 'Запоріжжя', 'Донецьк']
  • BFS шлях: ['Львів', 'Тернопіль', 'Хмельницький', 'Вінниця', 'Одеса', 'Херсон', 'Запоріжжя', 'Донецьк']

Пояснення різниці:

  • DFS (глибина-насамперед) шукає шлях, заглиблюючись у гілки графа, тому шлях має тенденцію до проходження через більше міст, особливо через ті, що мають менше з'єднань.

  • BFS (ширина-насамперед) шукає шлях з використанням ближчих сусідів на кожному кроці, тому знаходить коротший шлях (у кількості пройдених вершин) у порівнянні з DFS.