Message on Whatsapp 8879355057 for DSA(OA + Interview) + Fullstack Dev Training + 1-1 Personalized Mentoring to get 10+LPA Job
1 like 0 dislike
in Competitive-Programming by
edited by | 6,296 views

6 Answers

0 like 0 dislike
0 like 0 dislike

First learn the basic terminologies like nodes, edges, directed graphs, undirected graphs and how to represent each type of graph (adjacency matrix form and adjacency list form). Learn when to use which form. Google tutorial on basic graph theory and open the top links(google already gives best ones at the top). Read and understand each basic detail mentioned. After that read about basic graph traversals bfs and dfs. Read and understand their implementation (this is most important). Make sure you understand this by performing bfs and dfs yourself on some random graphs. Solve simple problems involving dfs and bfs on various online judges. You can find some here: Breadth First Search - Competitive Programming Algorithms and Depth First Search. After this learn how to detect cycle in both directed and undirected graph. Visit this link: Main Page - Competitive Programming Algorithms, go to graph section and learn different algorithms. The plus points about each tutorial are:

  1. The tutorials are arranged in increasing order of understanding of algorithm and implementation difficulty (in graph section).
  2. Each tutorial end with links to various practice problems thus providing an overview of different types of questions that involves use of that particular algorithm.

Practice as much questions as you can. My personal choice is codeforces. It contains a large variety of problems related to graph and practising there will surely help you have good grasp over the topic.

0 like 0 dislike
First you should know how can we make graphs in any programming language. Once you figure out how to make the graph then the next thing you need is to learn graphs algorithms. Start with basic first learn dfs/bfs practice on A2 Online Judge . Once you have cleared your concepts on dfs/bfs move on next algorithm that is Dijkstra and like that go on step wise step and in no time you will be expert in graphs
Happy coding!!!!!
0 like 0 dislike

Try the online tutorial for Indian IOI students:

  1. Basic Graph Algorithms
  2. Advanced Graph Algorithms

Along with the tutorials, there are also some example problems and solutions.

Topcoder Algorithm Tutorials also has a few introductory tutorials on Graph theory.

0 like 0 dislike
The most common advice: Practice.

The question that follows: How should I do? What should be done ? Which topic should be done first?

Let me try to create a step by step approach. First learn how to design a graph data structure. This is important as you will be using this design to solve your problem. Learn the most optimum representation of graph in adjacency matrix and adjacency list form. Then learn bfs and dfs to learn how to traverse the graph.

Bfs and dfs have vast area of applications e.g. given a matrix of numbers we can use bfs to find all numbers which are at odd distance from a given number or given a matrix of words we can use dfs to find all words that can be formed starting from given word. You will find more applications once you solve problems. Prefer solving problems from codeforces and topcoder starting from div2 250 pointers.

Then you can learn commonly used graph algos : minimum spanning tree (kruskal and prim), shortest path(dijkastra, bellman-ford), detect cycle in a graph, topological sorting of vertices, eulerian path and circuit, connected components, bipartite graph, strongly connected components. There are some other algos but they are rarely used.

One important question is still unaswered: How to approach a problem? First design the graph data structure on the basis of data provided in the problem statement. Then try to figure out whether bfs or dfs will be helpful in carrying out operations specified in question. Sometimes in case a graph is a tree then the tricky part is that neither dfs nor bfs can give optimum solution. In that case you can create a vector of edges and then process one edge at a time getting worst case linear time complexity as number of edges in a tree is one less than number of vertices.

Read the problem statement carefully and try to figure out which algo best suits the operations specified.
1 like 0 dislike
Graph theory is one of the most important topics in discrete math and programming. According to me, the most crucial step in solving graph theory problems is visualising them properly.

Most people will tell you "Go to XYZ website, sort problems by graph theory and start practicing". This has to be done any way for any topic. Let me tell you something more interesting. In this answer, I shall try to throw light on how you build intuition about graph problems and how you can know which approach to take. Let's go step wise:

Read the question very carefully for determining what type of graph it is:

This is the first and probably one of the most important steps. The question will tell you whether the graph is a tree, or it is a graph with only one cycle, or multiple disjoint cycles, or just a random graph. A tree has so many nice properties that you can exploit. There are subtle ways of saying that the given graph is a tree. For example: "The graph has N nodes. It is not disjoint and has N-1 edges", "The graph doesn't contain any cycles", "In the given directed graph, each node has one and only one parent", etc. Similarly, if there is only one cycle, then you can imagine the graph as having a ring with many trees hanging from the nodes of the ring.

Once the graph has been identified, identify what the question wants from you:

In this step, you try to figure out what is it that the question wants you to do. Does it have something to do with shortest paths? If yes, then are all the weights positive? If not, then clearly it can't be direct Dijkstra. What else can we do? Bellman Ford? Floyd-Warshall? You should be able to eliminate approaches fast.

Graph problems can also include simple traversal, flows, disjoint unions, etc. The best way to figure out what is applicable is method of elimination. The size of input data tells a lot about the algorithm to be used. This is because graph algorithms span the whole range of complexities, from linear to exponential. So, if you know you need a linear or a quasi-linear algorithm for the given size of input, you can simply eliminate many of the algorithms.

If you have identified that the graph is not a tree, a lot of algorithms can further be eliminated like heavy-light decomposition, dynamic programming on trees, centroid decomposition, etc, unless the question allows you to form a tree of biconnected components.

Coming up with an algorithm to solve the problem:

Once you have identified what the question is asking you to do, and what is the basic algorithm that is going to be used, the last step is to come up with a working solution. The best way according to me is to solve the problem with pen and paper. You construct small graphs of the kind that the question puts out, and you try to apply the techniques that you shortlisted from the previous section. This is because graph algorithms generally are quite good at scalability. What this means is that if you observe a particular property for a small graph that you draw on paper, it is highly likely that the property will be true for similar graphs of any size . So, by trying out techniques on paper, you can get to a solution in most of the cases.

Coding graph problems:

Graph problems are generally code intensive. But they follow a very standard pattern. This is the point where practice comes in. You need to code quite a few graph problems before you reach a stage of mastery. The biggest hurdle is coding what you have visualised since graph problems tend to be more abstract in nature than something like data structures or greedy algorithms. There is only one way to work around this hurdle: practice. The more you code, the better you become with putting your visualisation on to your editor.

This is all I can think of at this point in time. I shall edit this answer if I feel I missed something.

All the best :)