What is the uniform-cost search (UCS) algorithm? How does it work? I would appreciate seeing a graphical execution of the algorithm. How does the frontier evolve in the case of UCS?
Uniform Cost Search is also called the Cheapest First Search. For an example and entire explanation you can directly go to this link: Udacity - Uniform Cost Search.
In this answer I have explained what a frontier is. To put it in simple words you can describe UCS algorithm as 'expanding the frontier only in the direction which will require the minimum cost to travel from initial point among all possible expansions' i.e. adding a point on the graph (which can be reached from the frontier without going through any other point) which has the shortest route from the initial point. We keep on doing this until a path has explored the goal frontier, this path is the cheapest path from the initial point.
I strongly suggest you check out both the links for examples and better understanding.
NOTE: I have added a YouTube URL in the comments for those who do not want to sign in.