Depth First Search (DFS) ալգորիթմ

Պատկերացրեք, որ ղեկվարում եք մի ռոբոտի, որը գտնվում է գրաֆի某 դիրքում, որտեղ կա n κορուկ (գագաթ) և e կող։ Դուք ուզում եք սկսել某 գագաթից և հերթով անցնել գրաֆի բոլոր այն գագաթներով, որոնք հասանելի են սկզբնական կետից։ Depth First Search (DFS) ալգորիթմը հենց այդ նպատակին է ծառայում. այն սկսում է某 գագաթից, ընտրում է某 ճանապարհ ու գնում մինչև այն гագաթ, որտեղ այլևս հնարավոր չէ շարունակել, ապա “վերադառնում” է նախորդ գագաթ ու փորձում նոր ճանապարհներ։

DFS ալգորիթմը պատկերացնելիս կարելի է մտածել փոքրիկ ռոբոտի մասին, որը սկսում է某 գագաթից և տեսնում է միայն текմ الحالية գագաթի հարևաններին և այն գագաթները, ուր ինքն արդեն գնացել է (և հիշում է այդ ողջ ճանապարհը): Այս պրոցեսը ռեկուրսիվ է. յուրաքանչյուր փուլում ռոբոտը գնալու է某 նոր գագաթ, որտեղ դեռ չի եղել, ու նույնը կրկնելու է մինչև այլևս չլինեն չայցելված գագաթներ այդ ուղղությամբ։ Հետո ռոբոտը “վերադառնում” է նախորդ կետ, որպեսզի շարունակի նույն գագաթի մնացած հարևանների ուսումնասիրությունը։ Այս միտքը շատ է օգնում ալգորիթմի իրականացմամբ (ռեալիզացիայով) զբաղվելիս։

DFS ալգորիթմի իրագործումը կարելի է անել ռեկուրսիայի միջոցով, որտեղ մենք հետևում ենք текущ гագաթին (նշենք այն v-ով), ինչպես նաև այն գագաթների ցուցակին, որոնք արդեն օգտագործվել են (նշենք used-ով).

import sys

sys.setrecursionlimit(10 ** 6)          # Մեծացնում ենք ռեկուրսիայի սահմանը, որպեսզի DFS-ն աշխատի առանց խնդիրների

n, e = map(int, input().split())        # n: գագաթների քանակը, e: կողերի քանակը
g = [[] for _ in range(n)]              # գրաֆի adjacency list ներկայացում
used = [False] * n                      # այցելված (օգտագործված) գագաթներ

for _ in range(e):                      # ընթերցում ենք կողերը
    a, b = map(int, input().split())    # a -> b և b -> a (անուղղորդ գրաֆ)
    g[a].append(b)
    g[b].append(a)


def dfs(v):                             # խորությամբ որոնում
    used[v] = True                      # նշում ենք, որ գագաթը այցելված է
    print(v, end=' ')                   # տպում ենք գագաթը
    for to in g[v]:                     # անցնում ենք v-ի բոլոր հարևաններով
        if not used[to]:                # եթե գագաթը դեռ չի օգտագործվել
            dfs(to)                     # անում ենք dfs այդ գագաթի համար


start = int(input())                    # մեկնարկային գագաթ
dfs(start)                              # կանչում ենք dfs մեկնարկային գագաթի համար

Առաջին հերթին սկզբնական փուլում初始化 ենք գրաֆը, ևTraversal-ը սկսում ենք start գագաթից։ Սկզբում used զանգվածի բոլոր արժեքները False են։ Երբ այցելում ենք某 գագաթ, սկզբում դրան նշանակում ենք used[v] = True (նշելով, որ այն արդեն այցելված է), հետո անցնում ենք текущ գագաթի v բոլոր հարևաններին։

Ուշադրություն դարձրեք, թե ինչպես է ռեկուրսիան գործում որպես “ճանապարհի” ուսումնասիրող․ երբ ալգորիթմը “չունի” էլ հետագա չիրացվող գագաթներ某 ուղղությամբ, այն վերադառնում է (բեքթրեք) նախորդ դրվագի գագաթ, որպեսզի այնտեղից继续 ուսումնասիրել մնացած հարևանները։ Այդ բեքթրեքն էլ հենց ռեկուրսիայի ավարտման պահն է։

Եկեք մոդելավորենք ալգորիթմի գործողությունը մի քանի օրինակով.

Առաջադրանք: Հաշվել գրաֆում կապված կոմպոնենտների քանակը

Տրված է անուղղորդ գրաֆ, որն ունի v գագաթ և e կող։ Պահանջվում է հաշվել գրաֆի կապված կոմպոնենտների քանակը։ Եթե某 միավոր գագաթներ փոխադարձ անցումներով հասանելի են մեկը մյուսին, ապա դրանք պատկանում են同 կապված կոմպոնենտին։

Մուտք

Մուտքի առաջին տողում ներառված են երկու ամբողջ թվեր v (1 ≤ v ≤ 100 000) և e (1 ≤ e ≤ 100 000):

Հաջորդ e տողերում տրվում են զույգերով թվեր v1, v2 (1 ≤ v1, v2 ≤ v), որոնք նշում են, որ գագաթ v1-connected է գագաթ v2-ին և հակառակը։

Ելք

Ծրագիրը պետք է տպի գրաֆի կապված կոմպոնենտների քանակը։

Օրինակներ