This is the 24th day of my participation in Gwen Challenge

The application of figure

Minimum spanning tree

The spanning tree with the minimum sum of the weights of all spanning trees, assuming that the weights of the edges are different

The nature of the

  • The minimum spanning tree is not unique. If edge weights are not equal, the minimum spanning tree is unique
  • The minimum spanning tree weight sum is unique
  • The minimum number of edges in the spanning tree is -1

General algorithm

GENERIC_MST(G){
    T=NULL;
    whileT does not form a spanning treedoFinding a minimum cost edge (u,v) and adding T does not create a loop (T=T∪(u,v); }Copy the code

Prim algorithm

void Prim(G,T){
    T=NULL; // Initialize the empty tree
    U={w};  // Add any vertex w
    while((V-U)! =0){find (u,v) such that u belongs to u and v belongs to (v-u). Vertices go into}}Copy the code

Prim algorithm complexity is O (| V | ^ ^ 2), and has nothing to do with the number of edges, so is suitable for the solution and dense minimum spanning tree of the graph

Kruskal algorithm

void Kruskal(V,T){ T=V; numS=n;// Initialize the tree, the number of connected components
    while(numS>1){take the edge with the least weight from E;if(v and u belong to different connected components){edge subsume; numS--; }}}Copy the code

The time complexity O (log | E |)

The shortest path

For unauthorized maps: breadth-first search

For entitlement map:

  • Monophyletic shortest path: the Dijkstra algorithm, time complexity O (| V | ^ ^ 2)
  • Find the shortest path of each pair of vertices: floyd-Warshall

Floyd-Warshall

  • Time complexity O (| V | ^ 3 ^)
  • Negative-weighted edges are allowed, but loops containing negative-weighted edges are not allowed

A topological sort

  • Directed acyclic graph DAG graph
  • AOV net: Projects are represented using DAG, where vertices represent activities and directed edges indicate that activity Vi must precede activity VjV_i must precede activity V_jVi must precede activity Vj

Conditions that must be met for topology sorting

  • Each vertex occurs only once
  • If vertex A precedes vertex B in the sequence. There is no path B — >A

Common way of thinking

  • Select a graph with no precursor nodes and print it
  • Delete this node and all edges that use it as a node

If you find that there are not enough nodes, there are loops

The critical path

  • AOE net: events are represented by vertices, activities are represented by directed edges, and costs of activities are represented by weights of edges
  • AOE network has only one vertex with an entry degree of 0, called the beginning vertex (source point), and only one vertex with an exit degree of 0, called the end vertex (convergence point).
  • The path with the maximum path length from the source point to the sink point is the critical path, the activities on the critical path are called critical activities, and the shortest time to complete the whole project is called the critical path length