Simple Graphs

В тази секция ще разгледаме може би най-фундаменталната тема в състезателното програмиране - а именно теория на графите. Ще научим как да представяме графи в паметта по няколко различни начина. Ще разгледаме основните алгоритми за обхождане и търсене в графи: търсене в ширина, търсене в дълбочина, и алгоритъма на Дейкстра. Ще видим какво е минимално покриващо дърво, непресичащи се множества, топологично сортиране. Ще видим и една техника, която помага не само в графови задачи: разширяване на графа.

Темите, които биха ви били полезни за тази секция са Графи и представяне на графи, Търсене в дълбочина, Търсене в ширина, и Алгоритъм на Дейкстра,

Откъм задачи това е една от най-дългите секции, като повечето алгоритми са покрити от поне две задачи (а по-основните - дори от повече). В повечето задачи се изисква директна имплементация или съвсем дребна модификация.