[go: up one dir, main page]
Scribd
Upload
51 views3 pages

Time and Space Complexity For Graph Algorithms

The document outlines various graph algorithms, detailing their time and space complexities. Algorithms include BFS, DFS, Topological Sort, SCC, Dijkstra’s, Bellman-Ford, Prim’s, Kruskal’s, Floyd-Warshall, and Johnson’s. Each algorithm is characterized by its performance metrics in terms of vertices (V) and edges (E).

Uploaded by

abulhasananik2
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
51 views3 pages

Time and Space Complexity For Graph Algorithms

The document outlines various graph algorithms, detailing their time and space complexities. Algorithms include BFS, DFS, Topological Sort, SCC, Dijkstra’s, Bellman-Ford, Prim’s, Kruskal’s, Floyd-Warshall, and Johnson’s. Each algorithm is characterized by its performance metrics in terms of vertices (V) and edges (E).

Uploaded by

abulhasananik2
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

●​ V = number of vertices​

●​ E = number of edges​

●​ logV = logarithm of V​

●​ For weighted graphs: assume edge weights are integers or real numbers.​

1. BFS (Breadth-First Search)

●​ Time: O(V + E)​

●​ Space: O(V) (for visited array + queue)​

2. DFS (Depth-First Search)

●​ Time: O(V + E)​

●​ Space: O(V) (recursion stack + visited array)​

3. Topological Sort using DFS

●​ Time: O(V + E)​

●​ Space: O(V) (stack + visited array)​

4. Topological Sort using BFS (Kahn’s Algorithm)

●​ Time: O(V + E)​


●​ Space: O(V) (in-degree array + queue)​

5. SCC using Kosaraju’s Algorithm

●​ Time: O(V + E)​

●​ Space: O(V + E) (graph + transpose graph + visited)​

6. Articulation Point & Bridge using Tarjan’s Algorithm

●​ Time: O(V + E)​

●​ Space: O(V) (discovery time, low time, parent arrays)​

7. Dijkstra’s Algorithm

●​ Time:​

○​ Using min-heap (binary heap): O((V + E) log V)​

○​ Using Fibonacci heap: O(E + V log V) (theoretically better but rarely used in
practice)​

●​ Space: O(V) (distance array + min-heap)​

8. Bellman-Ford Algorithm

●​ Time: O(V * E)​

●​ Space: O(V) (distance array)​


9. Prim’s Algorithm

●​ Time:​

○​ Using min-heap: O((V + E) log V)​

○​ Using adjacency matrix: O(V^2)​

●​ Space: O(V) (priority queue + MST set)​

10. Kruskal’s Algorithm

●​ Time: O(E log E) (or O(E log V) if using Union-Find with path compression)​

●​ Space: O(V) (for Union-Find structure)​

11. Floyd-Warshall Algorithm

●​ Time: O(V^3)​

●​ Space: O(V^2) (distance matrix)​

12. Johnson’s Algorithm

●​ Time: O(V * E + V log V)​

○​ Uses Bellman-Ford (O(V * E)) + Dijkstra from every node (O(V * (E + V


log V)))​

●​ Space: O(V^2) (distance matrix)

You might also like