Графтағы алгоритм түрлері

Анықтама
DFS (тереңнен іздеу) — бір тармақты соңына дейін өтіп зерттейді (рекурсия/стек). BFS (көлденеңінен іздеу) — деңгей-деңгей зерттейді (кезек).

def dfs(v):
    visited[v] = True
    for w in adj_list[v]:
        if not visited[w]:
            dfs(w)

Ескеру
«Тойымсыз» (greedy) алгоритм әр қадамда жергілікті ең жақсы таңдауды жасайды, бірақ ЖАЛПЫ оптимал болмауы мүмкін.

Алгоритм	Не табады
Прима-Крускал	Минималды ішкі ағаш
Дейкстра	Бір жұп арасындағы қысқа жол
Флойд	Барлық жұп арасындағы қысқа жол

Деңгей: Орта

Тойымсыз алгоритм

Берілді: A→C(9), C→F(2), F→E(9) және A→B(7), B→C(10), C→F(2), F→E(9).

Табу керек: қысқа жол.

Шешуі:
A-C-F-E = 9+2+9=20, ал тойымсыз A-B-C-F-E = 7+10+2+9=28.

Жауабы: оңтайлы жол — 20, тойымсыз — 28.