Scribd
Upload
1 views1 page

Graph Algorithms Study Notes

The document provides a comprehensive overview of graph algorithms, including types of graphs, representations, and traversal methods such as DFS and BFS. It details various shortest path algorithms, minimum spanning tree methods, and techniques for cycle detection and strongly connected components. Additionally, it summarizes algorithm complexities and offers interview tips for applying these concepts effectively.

Uploaded by

abhilasa.infinity
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
1 views1 page

Graph Algorithms Study Notes

The document provides a comprehensive overview of graph algorithms, including types of graphs, representations, and traversal methods such as DFS and BFS. It details various shortest path algorithms, minimum spanning tree methods, and techniques for cycle detection and strongly connected components. Additionally, it summarizes algorithm complexities and offers interview tips for applying these concepts effectively.

Uploaded by

abhilasa.infinity
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

Graph Algorithms - Detailed Study Notes

1. Introduction
A graph is a data structure consisting of vertices (nodes) and edges connecting them. Types:
directed, undirected, weighted, unweighted, cyclic, acyclic, connected, disconnected.

2. Representations
Adjacency List: O(V+E) space, efficient for sparse graphs.
Adjacency Matrix: O(V²) space, efficient edge lookup.

3. Traversals
DFS: Stack/recursion, O(V+E). Applications: cycle detection, topological sort, SCC.
BFS: Queue, O(V+E). Applications: shortest path in unweighted graphs, level order.

4. Shortest Path Algorithms


Dijkstra: Non-negative weights, O((V+E)logV).
Bellman-Ford: Handles negative edges, detects negative cycles, O(VE).
Floyd-Warshall: All-pairs shortest paths, O(V³).

5. Minimum Spanning Tree


Kruskal's Algorithm: Sort edges + Union-Find, O(E logE).
Prim's Algorithm: Priority queue, O(E logV).

6. Topological Sort
For DAGs only. Methods: DFS and Kahn's Algorithm.

7. Cycle Detection
Undirected: DFS or Union-Find. Directed: DFS recursion stack or Kahn's Algorithm.

8. Strongly Connected Components


Kosaraju and Tarjan algorithms.

9. Maximum Flow
Ford-Fulkerson and Edmonds-Karp.

10. Complexity Summary


BFS/DFS: O(V+E), Dijkstra: O((V+E)logV), Bellman-Ford: O(VE), Floyd-Warshall: O(V³), Kruskal:
O(ElogE), Prim: O(ElogV).

Interview Tips
Know when to use BFS vs DFS, choose shortest-path algorithm based on edge weights,
understand Union-Find, priority queues, and DAG concepts.

You might also like