Definitions
Graph theory is a fundamental concept in computer science, especially for competitive programming. Here’s an overview of essential graph concepts:
Key Concepts
- Vertices and Edges: Graphs consist of nodes (vertices) connected by edges.
- Directed vs. Undirected Graphs: Directed graphs have edges with a direction, while undirected graphs do not.
Common Algorithms
- Depth-First Search (DFS): Explore as far as possible along a branch before backtracking.
- Breadth-First Search (BFS): Explore all neighbors at the present depth before moving on to nodes at the next depth level.
Understanding these concepts will enhance your ability to tackle graph-related problems in contests.