4-деңгээл. Графтар жана динамикалык программалоо

Графтарды кыдыруу, эң кыска жолдор, каркас дарактары жана динамикалык программалоо боюнча алгачкы маселелер.

Орто деңгээлдин эки киттери: графтар (DFS, BFS, Дейкстра, каркастар) жана динамикалык программалоо. Ушул деңгээлден «чыныгы» олимпиадалык алгоритмика башталат — жана шаардык, республикалык турлардын маселелеринин көпчүлүгү. 5-деңгээлге даярдыктын критерийи: тексттик маселени графка өз алдынча алып келесиз жана абал менен өтүү эмне экенин түшүндүрүп туруп, жөнөкөй ДПларды (тепкич, кесиндилер) чечесиз.

Бул бөлүмдө

  1. 1
    Графтар: сактоо, BFS жана DFS

    Графтар: чектештик тизмеси, тереңдеп жана туурасынан кыдыруу, байланыш компоненттери жана эң кыска жолдор.

  2. 2
    Эң кыска жолдор: Дейкстра жана Флойд

    Салмактуу графта эң кыска жолдор: O(m log n) убакыттагы Дейкстра жана O(n³) убакыттагы Флойд.

  3. 3
    Минималдуу каркас дарагы

    Минималдуу каркас дарагы: Краскалдын алгоритми = кырларды иреттөө + DSU.

  4. 4
    Динамикалык программалоо: негиздер

    Динамикалык программалоо: абалдар, өтүүлөр, база — тепкич жана максималдуу кесинди.

Доска