Algorithmes de graphes
Parcourez les algorithmes de graphes étape par étape et observez comment ils traversent les nœuds et les arêtes.
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.
Comparaison de Algorithmes de graphes
| Algorithme | Temps | Espace | Résout | Pondéré |
|---|---|---|---|---|
| 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 |