You get a bonus - 1 coin for daily activity. Now you have 1 coin

Examples of tasks in graphs

Lecture



In this section, you will be able to get acquainted with applied problems that are solved using graphs. Some of the tasks have a structure, according to which it is enough just to choose the right algorithm and apply it to get an answer. The other part requires some modification of the original graph and a combination of several algorithms to solve. In any case, all the algorithms used are described in the theoretical part, which will help you to better understand the methods of solving problems.

Tasks

  • Chain [dfs]
  • Path [dfs]
  • Gears [search wide]
  • New Year's Party [maximum flow]
  • Cubes [maximum flow]
  • Game [max flow]
  • Rope Telegraph [Minimum Span Tree (Prim's Algorithm)]
  • Secret Pipes [Minimum Span Tree (Kruskal's algorithm)]
  • Subway [minimum spanning tree (Prima algorithm), depth search]
  • Network [minimal spar tree (Kruskal algorithm)]
  • Olympiad in Alchemy [Dijkstra's algorithm]
  • Walls [Floyd-Worshel algorithm]
  • Blockade [Dijkstra's algorithm]

For each task, a detailed description of the solution method, a formal algorithm, an analysis of examples, a program listing and a compiled solution file are attached.


Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Algorithms

Terms: Algorithms