Topic 14 of 15
Graph
Towns and roads.
A graph is a map of towns (nodes) and roads (edges). Roads can be one way or two way, and they can have lengths. To explore, you either fan out ring by ring with a waiting line (BFS), or follow one road as far as it goes before turning back (DFS).
What you will be able to do
BFS and DFSCycle detectionTopological sortShortest paths: BFS, Dijkstra, Bellman FordUnion find and spanning trees
0/43
Meet the graph
01 / 04
Five towns, six roads. Start at town A.
- looking now
- seen
- done
- answer
- path
- just added
The problems
In order from easier to harder ideas. The ones marked must do come up in interviews again and again.
- 01Create a Graph, print itWrite down who is friends with whom so you can quickly read out every kid and their friends.Adjacency list
- 02Implement BFS algorithmVisit every room of a building ring by ring: first the rooms next door, then the rooms two doors away, and so on.Breadth first search
- 03Implement DFS AlgoExplore a maze by walking down one tunnel as far as it goes, then stepping back to try the next tunnel.Depth first search
- 04Detect Cycle in Directed Graph using BFS DFS AlgoFollow one-way arrows between rooms and find out if some path of arrows leads you back where you started.Depth first search
- 05Detect Cycle in UnDirected Graph using BFS DFS AlgoWalk the hallways of a maze with chalk and find out if some hallways form a loop.Depth first search
- 06Search in a MazeA mouse at the top left corner of a maze lists every way to reach the cheese at the bottom right, never stepping on the same square twice.Backtracking
- 07Minimum Step by KnightFind the fewest L-shaped hops a chess knight needs to reach a target square on an N by N board.Breadth first search
- 08Flood fill algoUse the paint bucket: click one spot and recolor every touching spot that had the same color.Depth first search
- 09Clone a graphBuild a brand new copy of a web of friends, where every copy is friends only with other copies.Hash map from old to new
- 10Making wired ConnectionsCount how many cables you must unplug and replug so every computer in the office ends up on one network.Union find
- 11Word LadderTurn one word into another by changing one letter at a time, using only words from a list, in as few words as possible.Breadth first search
- 12Dijkstra algoFind the cheapest way from home to every place on a map by always finishing the closest unfinished place first.Dijkstra
- 13Implement Topological SortPut chores in an order where every chore comes after the chores it depends on, like socks before shoes.Topological sort
- 14Minimum time taken by each job to be completed given by a Directed Acyclic GraphEach job takes one minute and some jobs must wait for others, so find the earliest minute every job can be finished.Topological sort
- 15Find whether it is possible to finish all tasks or not from given dependenciesSome chores must wait for other chores; find out if there is an order that gets every chore done.Topological sort
- 16Find the no. of IslandsCount the separate patches of land on a map made of land and water squares.Depth first search
- 17Given a sorted Dictionary of an Alien Language, find order of charactersRead an alien picture dictionary and work out the order of their alphabet from clues between neighbouring words.Topological sort
- 18Implement Kruskals AlgorithmConnect every town using the cheapest roads: always build the cheapest road left, unless it joins two towns that are already connected.Union find
- 19Implement Prims AlgorithmGrow a road network from one town, always adding the cheapest road that reaches a town not yet connected.Greedy with a heap
- 20Total no. of Spanning tree in a graphCount how many different ways you can keep just enough rope bridges so every treehouse is reachable and no bridges form a loop.Matrix tree theorem
- 21Implement Bellman Ford AlgorithmFind the cheapest trip from home to every stop when some roads pay you back, and notice when a loop would pay you forever.Bellman Ford
- 22Implement Floyd Warshall AlgorithmFill a price table for every pair of towns by letting each town, one at a time, act as a stop in the middle.2D dynamic programming
- 23Travelling Salesman ProblemFind the shortest trip that leaves home, visits every friend exactly once to hand out party invitations, and comes back home.Bitmask dynamic programming
- 24Graph Colouring ProblemColour a map so neighbouring countries never share a crayon, using as few crayons as you can.Greedy colouring
- 25Snake and Ladders ProblemFind the fewest dice throws that get you from the first square of a snakes and ladders board to the last, if you could choose every roll.Breadth first search
- 26Find bridge in a graphFind every road that, if it washed away, would cut the map into two parts.Depth first search with low-link
- 27Count Strongly connected Components (Kosaraju Algo)Count the groups of kids where every kid can pass a note to every other kid in the same group, using one-way note routes.Depth first search, two passes
- 28Check whether a graph is Bipartite or NotCheck if a class can be split into two teams so that every pair of friends ends up on different teams.Breadth first search
- 29Detect Negative cycle in a graphFind out if some loop of toll roads pays you money every time you drive around it.Bellman-Ford
- 30Longest path in a Directed Acyclic GraphOn a hill of one-way slides, find the route from your start that collects the most points to every stop.Topological sort
- 31Journey to the MoonGroup astronauts into countries from pairs of teammates, then count the ways to pick two astronauts from different countries.Union find
- 32Cheapest Flights Within K StopsFind the cheapest trip between two cities when you may change planes only a few times.Bellman-Ford with limited rounds
- 33Oliver and the GameAnswer many questions of the form: is this house on the road between that house and the castle, in a town whose roads form a tree.Depth first search
- 34Water Jug problem using BFSWith a 4 cup jug and a 3 cup jug and a tap, find the fewest fills, empties and pours that leave exactly 2 cups in one jug.Breadth first search
- 35Find if there is a path of more than k length from a sourceGo on a hike from a start point, never visiting a spot twice, and check if some hike is at least k long.Backtracking
- 36M-Colouring ProblemWith only m crayons, decide whether a map can be coloured so that no two neighbouring countries match.Backtracking
- 37Minimum edges to reverse to make path from source to destinationFind the fewest one-way streets you must flip so you can drive from home to a friend, by making right-way streets free and wrong-way streets cost one.0-1 breadth first search
- 38Paths to travel each nodes using each edge (Seven Bridges)Decide if you can take a walk that crosses every bridge exactly once, like drawing a picture without lifting your pencil, and find that walk.Euler path (Hierholzer)
- 39Vertex Cover ProblemPut the fewest cameras in rooms so that every hallway has a camera at one of its two ends.Backtracking
- 40Chinese Postman or Route InspectionWalk down every path in the park at least once and come back to the gate, walking as little as possible.Euler circuit plus bitmask matching
- 41Number of Triangles in a Directed and Undirected GraphCount the groups of three kids who are all friends with each other, or the three-way loops of one-way arrows.Degree ordering
- 42Minimise the cashflow among a given set of friends who have borrowed money from each otherAfter a trip full of small loans between friends, settle up with as little money changing hands as possible.Greedy
- 43Two Clique ProblemDecide if a class can be split into two teams where everyone on a team is friends with everyone else on that team.Bipartite check