常见图论算法的时间复杂度

12 个常见图论算法的时间复杂度。

---

Dijkstra's Algorithm

$O(V^2)$ for the basic version with an adjacency matrix representation, where $V$ is the number of vertices. With a binary heap (priority queue), it improves to $O((V + E) \log V)$, and with a Fibonacci heap, it further improves to $O(E + V \log V)$, where $E$ is the number of edges.

A* Search Algorithm

$O(E)$, but this is highly heuristic-dependent. With a perfect heuristic, it's as efficient as possible. Usually, it behaves similarly to Dijkstra's algorithm in terms of complexity, because it is essentially Dijkstra's algorithm with heuristics.

Bellman-Ford Algorithm

$O(V \cdot E)$, where $V$ is the number of vertices and $E$ is the number of edges. This is because it relaxes all $E$ edges $V-1$ times.

Floyd-Warshall Algorithm

$O(V^3)$, where $V$ is the number of vertices. This is because it considers all pairs of vertices and iterates through all possible intermediate vertices for each pair.

Breadth-First Search (BFS)

$O(V + E)$ for both adjacency list and adjacency matrix representations of the graph.

Depth-First Search (DFS)

$O(V + E)$ for both adjacency list and adjacency matrix representations of the graph.

Kruskal's Algorithm (for MST)

$O(E \log E)$ or $O(E \log V)$, since sorting of edges is required, which takes $O(E \log E)$ and the union-find operations take $O(E \log V)$.

Prim's Algorithm (for MST)

Similar to Dijkstra's algorithm, $O(V^2)$ with a basic version, $O((V + E) \log V)$ with a binary heap, and $O(E + V \log V)$ with a Fibonacci heap.

Tarjan's Algorithm (for Strongly Connected Components)

$O(V + E)$, since it is essentially a DFS with additional bookkeeping.

Edmonds-Karp Algorithm (for Maximum Flow)

$O(V \cdot E^2)$, because in the worst case, each augmentation of flow can affect all edges, and there can be $V$ augmentations per edge.

Ford-Fulkerson Algorithm (for Maximum Flow)

$O(E \cdot f)$, where $f$ is the maximum flow in the graph. This is because the algorithm finds augmenting paths and might do so for each unit of flow.

Johnson's Algorithm (for All-Pairs Shortest Paths):

$O(V^2 \log V + VE)$, which combines the efficiency of Dijkstra's algorithm with a preprocessing step that reweights edges to allow for non-negative weights.