This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money. Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

The application of graph theory

Minimum spanning tree

There are two methods: Prim algorithm and Kruskal algorithm, and kruskal algorithm is recommended for practical calculation.

  • Kruskal algorithm

All edges in the graph are sorted according to their weights from small to large, and the edge with the lowest weight is selected to determine whether it is a safe edge (that is, it does not constitute a ring) until n-1 edges are selected to form a minimum spanning tree. Minimum spanning tree is not unique, but the sum of weights are equal and minimum, only one can be required.

  • Kruskal algorithm

This algorithm can be called “edge addition method”. The initial minimum number of spanning tree edges is 0, and each iteration selects a minimum cost edge that meets the condition and adds it to the edge set of the minimum spanning tree.

  1. Sort all the edges in the graph in order of cost from smallest to largest;
  2. Consider the n vertices in the graph as a forest composed of independent N trees;
  3. Select edges from small to large in weight, and the two vertices UI,viui and vi connected by the selected edge should belong to two different trees, then become an edge of the minimum spanning tree, and merge the two trees as one tree.
  4. Repeat (3) until all vertices are in a tree or there are n-1 edges.

The shortest path

  • Calculate the shortest path from start to finish, the opposite of the critical path, not to be confused.
  • Method: Start from the starting point, deduce to the end point, each intermediate node through directly calculate the shortest path to the intermediate node, so recursively deduce to the end point, is the shortest path.

As shown in the figure above, starting with A, find the shortest distance from A to each point to get the final result{A(0), B(4), C(5), D (6), E (10), F (9), G (16)}.

Network and maximum traffic

The calculation of the maximum transport capacity from one node to another depends on the shortcomings of the transport capacity between nodes: first of all, how many paths are available, the maximum flow is equal to the sum of the maximum flow of all paths, and the maximum flow of each path is determined by the flow with the minimum transport capacity between nodes (short board decision).

Problem-solving tips:

  1. The minimum weight of each path is the maximum flow of this path. After each path, the remaining transport flow value of this path needs to be modified in real time. If it is 0, this link will be deleted.
  2. Repeat step 1 until there is no path connection from the starting point to the end point, and then add the traffic on each path to get the overall maximum traffic.