Алгоритмы на графах
Пройдите по алгоритмам на графах шаг за шагом и посмотрите, как они обходят вершины и рёбра.
Depth-First SearchWatch DFS dive as deep as it can down each branch before backtracking.Breadth-First SearchSee BFS explore a graph level by level, nearest nodes first.Topological SortWatch a DAG get linearized so every edge points forward in the order.Dijkstra's AlgorithmSee Dijkstra settle the nearest node each step to find shortest paths.Bellman-Ford AlgorithmSee Bellman-Ford relax every edge each pass to find shortest paths.Kruskal's AlgorithmWatch Kruskal add the cheapest edges that never form a cycle.Prim's AlgorithmSee Prim grow a spanning tree by adding the cheapest crossing edge.
Сравнение: Алгоритмы на графах
| Алгоритм | Время | Память | Решает | Взвешенный |
|---|---|---|---|---|
| Depth-First Search | O(V + E) | O(V) | Traversal | No |
| Breadth-First Search | O(V + E) | O(V) | Traversal / shortest path | No |
| Topological Sort | O(V + E) | O(V) | Ordering (DAG) | No |
| Dijkstra's Algorithm | O((V + E) log V) | O(V) | Shortest path | Yes (non-negative) |
| Bellman-Ford Algorithm | O(V · E) | O(V) | Shortest path | Yes (± weights) |
| Kruskal's Algorithm | O(E log E) | O(V) | Minimum spanning tree | Yes |
| Prim's Algorithm | O(E log V) | O(V) | Minimum spanning tree | Yes |