Graph Theory examines graphs, which are structures made of vertices (nodes) and edges connecting them, crucial for analyzing complex networks and relationships.

Graph Representations

1. Adjacency Matrix: A grid where each cell (i, j) shows the presence or weight of an edge between vertices i and j. It provides quick edge lookups but can be memory-intensive for large or sparse graphs.
2. Adjacency List: A collection of lists where each vertex has a list of adjacent vertices. This representation is more space-efficient for sparse graphs and facilitates easy neighbor traversal.

Graph Traversal Algorithms

1. Depth-First Search (DFS): Explores as deeply as possible along each branch before backtracking. It’s useful for tasks like finding paths and topological sorting.
2. Breadth-First Search (BFS): Examines all neighboring vertices level by level, ideal for finding the shortest path in unweighted graphs and exploring node layers.

Shortest Path Algorithms

1. Dijkstra’s Algorithm: Finds the shortest paths from a source to all other vertices in graphs with non-negative weights, using a priority queue for efficiency.
2. Bellman-Ford Algorithm: Computes shortest paths in graphs with negative weights and detects negative weight cycles, handling more complex cases.

These concepts are fundamental for solving problems in network analysis and route optimization.