Introduction to Graph

• Graph terminology: vertices, edges, degree, paths, cycles.

• Types of graphs: directed, undirected, weighted, unweighted.

Graph Representations

• Adjacency matrix.

• Adjacency list.

• Comparison of representations.

Graph Traversals

• Breadth-First Search (BFS)

  1. Algorithm and applications.

• Depth-First Search (DFS)

  1. Algorithm and applications.

Shortest Path Algorithms

• Dijkstra's Algorithm

  1. Greedy approach.

  2. Implementation details.

• Bellman-Ford Algorithm

  1. Handling negative weights.

  2. Comparison with Dijkstra's.

Other Graph Algorithms

• Topological Sort

  1. Use in scheduling problems.

• Minimum Spanning Trees

  1. Kruskal's Algorithm.

  2. Prim's Algorithm.

Advanced Topics (if time allows)

• A* Algorithm

  1. Heuristic search.

• Strongly Connected Components

Applications of Graph Algorithms

• Network routing, social networks, dependency resolution.

Complexity Analysis of Graph Algorithms

• Time and space complexity.