Shulou(Shulou.com)06/03 Report--

This article introduces the Kruskal algorithm to find the minimum spanning tree of the complete C code, the content is very detailed, interested friends can refer to, hope to be helpful to you.

Basic idea of algorithm

An algorithm for finding the minimum spanning tree of weighted connected graphs. The kruskal algorithm selects a total of n-1 edges, and the greedy criterion is to select an edge with the least cost from the remaining edges that will not produce a loop to join the set of selected edges. Note that it is impossible to form a spanning tree if the selected edge produces a loop. The kruskal algorithm is divided into e steps, where e is the number of edges in the network. Consider the e edges in the order of increasing cost, one edge at a time. When considering an edge, if a loop appears when it is added to the set of selected edges, it is discarded, otherwise, it is selected.

The code is represented by adjacency matrix and edge set, so the code will be greatly simplified. There are many places in the code that can be optimized because they are only used to learn algorithms, not to optimize them.

Complete C code / * Kruskal algorithm for minimum spanning tree * / # include # define MaxSize 20typedef char VertexType;typedef struct Graph {/ / defines the adjacency matrix representation structure of the graph VertexType ver [MaxSize+1]; int edg [MaxSize] [MaxSize];} Graph;typedef struct gEdge {/ / defines an edge set structure to store all edge information int begin; int end of the graph Int weight;} gEdge;void CreateGraph (Graph * g) / / the generating function of the adjacency matrix method graph {int I = 0; int j = 0; int VertexNum; VertexType Ver; printf ("Please enter the vertices of the graph:\ n"); while ('\ n'! = (Ver=getchar () {g-> ver [iTunes +] = Ver G-> ver [I] ='\ 0mm; VertexNum = strlen (g-> ver); printf ("Please enter the corresponding adjacency matrix:\ n"); for (iTun0; I)

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.