Графтар: сактоо, BFS жана DFS
Графтар: чектештик тизмеси, тереңдеп жана туурасынан кыдыруу, байланыш компоненттери жана эң кыска жолдор.
Граф — кырлар менен байланышкан чокулар: шаарлар менен жолдор, адамдар менен достуктар, абалдар менен өтүүлөр. Маселелердин эбегейсиз катмары граф тилинде түзүлөт.
Сактоо: чектештик тизмеси — ар бир чоку үчүн анын кошуналарынын тизмеси. Векторлордун вектору g, мында g[v] — v чокусунун кошуналары. n×n чектештик матрицасы кичине n үчүн гана жарайт.
Эки негизги кыдыруу:
• DFS (тереңдеп): кыр боюнча мүмкүн болушунча жүрөбүз, анан артка кайтабыз. Рекурсия менен табигый жазылат. Колдонулушу: байланыш компоненттери, циклдерди издөө, топологиялык иреттөө.
• BFS (туурасынан): кезек аркылуу «толкундар» менен кыдырабыз. Салмаксыз графта эң кыска аралыктарды берет.
DFS: байланыш компоненттеринин саны. Киргизиңиз: 6 3, андан кийин кырлар: 1 2, 2 3, 4 5
Мисалда {1,2,3}, {4,5} чокулары жана жалгыз {6} — үч компонент.
BFS баштапкы чокуну кезекке салат, анан кайталайт: чокуну алдык — бардык кирбеген кошуналарын коштук. Чокулар старттан алыстыгы боюнча иштетилет, ошондуктан dist туура эсептелет.
BFS: 1-чокудан аралыктар. Киргизиңиз: 5 4, андан кийин кырлар: 1 2, 2 3, 3 4, 1 5
Эки кыдыруу тең — O(V + E): ар бир чоку жана ар бир кыр бир жолу иштетилет.
Баары баса турган тырмоолор:
1. Унутулган visited белгиси — чексиз цикл.
2. 10⁵+ чокудан турган чынжырда рекурсивдүү DFS стекти толтуруп салышы мүмкүн — өз стегиңиз менен итеративдик вариантты жазыңыз же лимитти көбөйтүңүз.
3. dist -1 менен инициализацияланат («болгон жокмун»), жана дал ушул маани — жетпеген чокулар үчүн даяр жооп.
Тапшырма: чекиттер жана решёткалардан турган n×m лабиринт — кирүүдөн чыгууга чейинки эң кыска жолду табыңыз (клеткалар боюнча BFS: кошуналар — төрт тарап).
Сабакты өттүм деп белгилеңиз.