BFS және DFS екілік ағашқа арналған


Күрделілік дәрежесі оңай
Жиі кіреді Amazon Infosys MAQ TCS
Бірінші іздеу Тереңдікті бірінші іздеу теория ағаш

Бірінші іздеу (BFS)

Біз бұған дейін білеміз бе BFS дегеніміз не? егер олай болмаса, өзіңізді жаман сезінудің қажеті жоқ, мақаланы толығымен оқып, алдыңғы мақаламызға кіріңіз Бірінші іздеу жақсы түсіну үшін. BFS - бұл деңгей реверстері, біз екілік ағаштың түйіндеріне солдан оңға қарай әр деңгейде барамыз.

А қолдану арқылы Кезек деректер құрылымы, біз деңгейлік реверсті табамыз. Біз түбірден бастаймыз, содан кейін BFS-ке түбір енгіземіз және сол түйіннің барлық көршілерін кезекке қоямыз. Осыдан кейін түйінді кезектен шығарып, егер ол келмеген болса, оны BFS қосыңыз және кезекке көршіңіздің (шақырылмаған) қосыңыз. Кезектің өлшемі нөлге тең болмайынша, оны қайталаңыз.

Тереңдікті бірінші іздеу (DFS)

Біз DFS дегеніміз не екенін білеміз бе? Біздің алдыңғы мақаламызға кіруге болады Тереңдікті бірінші іздеу. БТ DFS - бұл жүрудің үш түрі:

  1. Алдын ала тапсырыс беру
  2. Inorder Traversal
  3. Постерден өту

Алдын ала тапсырыс беру

Algorithm:
Preorder(root):
Step:1 Print the data of the Node.
Step:2 Move to the left side of the node(traverse left-subtree).
Step:3 Move to the right side of the node(traverse right-subtree).

Inorder Traversal

Algorithm: 
Inorder(root): 
Step:1 Move to the left side of the node(traverse left-subtree).
Step:2 Print the data of the Node.  
Step:3 Move to the right side of the node(traverse right-subtree).

Постерден өту

Algorithm: 
Postorder(root):  
Step:1 Move to the left side of the node(traverse left-subtree). 
Step:2 Move to the right side of the node(traverse right-subtree).
Step:3 Print the data of the Node.

Dегер екілік ағаштың BFS және DFS арасында

Қолданылатын мәліметтер құрылымының түрі

BFS-де біз а құйрық типтік мәліметтер құрылымы және DFS-де біз а Стек типтік мәліметтер құрылымы.

Ғарыштың күрделілігі

BFS-де біз деңгей элементтерін сақтау үшін кезекті қолданамыз, сондықтан BFS-де максималды кеңістік қолданылады O (w) мұндағы w - бір деңгейдегі максималды элемент. DFS-де біз стек қолданамыз және тереңдік тұжырымдамасын ұстанамыз. Сонымен, ағаштың максималды биіктігі бағалау үшін максималды орын алады. Демек, DFS ғарыштық күрделілігі O (H) мұндағы H - ағаштың биіктігі.

Уақыттың күрделілігі

Уақыт екі жағдайдың күрделілігі O (N + E) болады, мұндағы N BT-дегі жалпы түйіндерді, ал E - BT-дегі толық жиектерді білдіреді.

Түбір түйініне жақын түйінді іздеу

Жақсы нәтижеге жету үшін біз BFS-ті тамырдың түйініне жақын түйіндер типін іздейміз, өйткені ол деңгей ревервалына сәйкес келеді.

Түбірлік түйіннен алыс түйінді іздеу

Жақсы нәтиже алу үшін біз бұл жағдайда DFS-ді қолданамыз, өйткені ол тереңдік тұжырымдамасына сәйкес келеді.

мағынасы

BFS Breadth - бірінші іздеуді, DFS - тереңдікті - бірінші іздеуді білдіреді.

Қолданылатын мәліметтер құрылымының түрі

BFS кезек типті деректер құрылымын және DFS Stack типті деректер құрылымын қолданды.

негізгі

BFS - бұл шыңға негізделген алгоритм, ал DFS - шеге негізделген алгоритм.

жылдамдық

BFS DFS-ге қарағанда баяу.

анықтамалық

Сұхбат сұрақтары