A Guide to Important Graph Algorithms for Competitive Programming
And how you can use DFS and BFS
If you’ve read an Introduction to Competitive Programming, then you’re probably familiar with why Competitive Programming is important. For those of you who haven’t, I believe that Competitive Programming is important because it helps you build your problem-solving skills and your technical knowledge of data structures and algorithms.
One of the biggest parts of Competitive Programming is learning the algorithms you need to succeed. I’ll be covering a large number of those algorithms in this post, specifically all the graph algorithms you’ll need to be successful in solving graph problems in Competitive Programming contests. Of course, just knowing the algorithms isn’t enough and you will have to complete a lot of practice problems on sites like Codeforces. However, this article will present you with the tools you need to master important graph algorithms.
What is a Graph?
In theoretical computer science, graphs are different from what you learned about in middle school. They are not bar charts.
Graphs in theoretical Computer Science and Discrete Mathematics are an abstract way of representing various types of relationships such as roads connecting cities and other types of networks. Graphs are made up of two components: edges and vertices. A vertex is a point on a graph and an edge is what connects two points on a graph.
Graph problems in competitive programming will usually be talking about things like networks and grids in the problem statement.
Here’s a list of all the graph terminology you need to know:
- Path: A sequence of edges which joins a sequence of distinct (different) vertices.
- Walk: Walks are paths, but they don’t require a sequence of distinct vertices.
- Cycle: A group of…
