Introduction to Graphs (and how to represent them)
I recommend watching the following videos for learning about graphs. These are really well made videos and he covers a lot in these short videos, so if you feel overwhelmed, use the rewind and pause buttons.
Introduction to Graphs
What are graphs? What are different types of graphs (directed and undirected, trees and DAGs, etc)? And examples of using them to model web links, flights between cities, and other things.
In the most of the text/video tutorials,vertices are always( as far as I've noticed) represented by integers ( from 0 to any positive integer). Is this always the case?? I ponder if we're dealing with real life,then vertices would be an object,right??
Motivation problem: We have a tree consisting of n(<=10^5) nodes. We will consider the tree nodes indexed from 1 to n. We will also consider the first node to be initially painted red, and the other nodes — to be painted blue. The distance between two tree nodes v and u is the number of edges in the shortest path between v and u. We need to learn how to quickly execute queries of two types:
paint a specified blue node in red;
calculate which red node is the closest to the given one and print the shortest distance to the closest red node.
Your task is to write a program which will execute the described queries.
Comments: It does seem like RMQ(Range Minimum/Maximum but on trees. Of course these can be solved using segment trees(Heavy Light Decomposition). But there is a technique which can be used to solved these kind of problems with the same time complexity but shorte...
The motivation for binary indexed trees is similar to that of segment trees. However, note that segment trees are much more flexible than binary indexed trees, and usually its true that any problem that can be solved with BIT can be solved with segment trees but not the other way around.
Video tutorial: This is a superb tutorial, giving the motivation, walking through example, and going step-by-step through the pseudocode.