优化性能 – 在图形上实现自定义算法

对于我的大学任务，我需要提出一种算法，找到具有相同权重的最大边数的生成树。 可以在此处找到任务的描述： 查找具有相同权重的最大边数的生成树 。 在那里你还可以看到我用C语言实现的upvoted解决方案（由@mrip建议）。

我已在本地计算机上测试了代码，并在不同的数据集上提供了正确的输出。 但是，当我将解决方案上传到高程系统时，我发现程序完成时间比参考时间长3倍。

这是项目中的两个文件。 我当然添加了详细的评论：

header.h

//struct for subsets used in MST Kruskal algoritm typedef struct subset { int parent; int rank; } subset_t, *subset_p; //struct for storing graph edges typedef struct edges { int src; int dest; int weight; } edges_t, *edges_p; //struct for storing weights and number of their occuriences typedef struct weights { int weight; int occurCount; } weights_t, *weights_p; //struct to store all built trees typedef struct trees { int totalWeight; // total tree weight int mostOccurNumber; // highest number of repeated edges for a tree } trees_t, *trees_p; //find and union function prototypes int find(struct subset subsets[], int i); void Union(struct subset subsets[], int x, int y); 

源代码.cpp

 #include  #include  #include "header.h" //find function used in Kruskals algorithm int find(subset_p subsets, int i) { if (subsets[i].parent != i) { subsets[i].parent = find(subsets, subsets[i].parent); } return subsets[i].parent; } //union function used in Kruskals algorithm void Union(subset_p subsets, int x, int y) { int xroot = find(subsets, x); int yroot = find(subsets, y); if (subsets[xroot].rank  subsets[yroot].rank) { subsets[yroot].parent = xroot; } else { subsets[yroot].parent = xroot; subsets[xroot].rank++; } } //compare function used in qsort(). Sorts all edges by ascending weight int myComp1 (const void *a, const void *b) { const edges_t * ptr_a = (const edges_t *)a; const edges_t * ptr_b = (const edges_t *)b; if (ptr_a->weight weight) return -1; if (ptr_a->weight > ptr_b->weight) return 1; return 0; } //Sorts all present weights by descending number of occuriences in the MST int myComp2 (const void *a, const void *b) { const weights_t * ptr_a = (const weights_t *)a; const weights_t * ptr_b = (const weights_t *)b; if (ptr_a->occurCount > ptr_b->occurCount) return -1; if (ptr_a->occurCount occurCount) return 1; return 0; } //Sorts all present MSTs primarily by descending number of same-weight occuriences //Secondly by ascending weights int myComp3 (const void *a, const void *b) { const weights_t * ptr_a = (const weights_t *)a; const weights_t * ptr_b = (const weights_t *)b; int diff = ptr_b->occurCount - ptr_a->occurCount; if (diff == 0) { if (ptr_a->weight weight) { diff = -1; } else if (ptr_a->weight > ptr_b->weight) { diff = 1; } else diff = 0; } return diff; } int main() { //number of vertices and edges for a graph int num_vertices, num_edges; scanf("%d%d", &num_vertices, &num_edges); // struct to keep all graph edges edges_p allEdges = (edges_p)malloc(num_edges*sizeof(edges_t)); //input variables for source vertex, destanation vertex and weight of the edge int curr_src, curr_dest, curr_weight; //array to store all present (different!) weight values int * weights = (int *)malloc(num_edges*sizeof(int)); //a variable to store number of elements in 'weights' array - number of different weight values in a graph int newWeightIndex = 0; //inputing data about graph edges: source vertex, destination vertex, weight for (int i = 0; i < num_edges; i++) { scanf("%d%d%d", &curr_src, &curr_dest, &curr_weight); //filling array of structs with input info allEdges[i].src = curr_src - 1; allEdges[i].dest = curr_dest - 1; allEdges[i].weight = curr_weight; //'Weights' array contains all weights that are present in a graph. //Here we decide whether we should put current weight value into an array. bool alreadyHasWeight = 0; for (int j = 0; j < i; j++) { if (weights[j] == curr_weight) { alreadyHasWeight = 1; break; } } if (alreadyHasWeight == 0) { weights[newWeightIndex] = curr_weight; newWeightIndex++; } } // end of data input //an array of structs to store info about build MSTs (the weight of MST and maximum number of edges with same weights) trees_p myTrees = (trees_p)malloc(newWeightIndex * sizeof(trees_t)); //Kruscal Algoritm lopp to find an MST for all present weights. //We take each weight in 'weights' and change the weight of every edge in a graph that has weight equal to 'weights[i]' to -1 for (int i = 0; i < newWeightIndex; i++) { int minimizedWeight = weights[i]; //array to store subsets of vertices subset_p subsets = (subset_p)malloc(num_vertices * sizeof(subset_t)); //array to store MST Edges edges_p mstEdges = (edges_p)malloc(num_vertices*sizeof(edges_t)); //array to store current edge edges_p currentEdge = (edges_p)malloc(sizeof(edges_t)); //variable to keep the amount of weight that was subtracted (when setting some weights to -1) //this is done in order to restore default weights after MST build finishes int subtractedWeight = 0; //variable to keep the number of edges which weight was changed to -1 int infEdgesTotal = 0; //variable to keep the number of edges which weight was changed to -1 included to MST int infEdgesTaken = 0; //setting minimum weights for (int i = 0; i < num_edges; i++) { if (allEdges[i].weight == minimizedWeight) { allEdges[i].weight = -1; subtractedWeight += minimizedWeight+1; infEdgesTotal++; } } //sorting all graph edges in ascending order qsort(allEdges, num_edges, sizeof(edges_t), myComp1); //the kruskal algoritm itself - BEGINNING for (int v = 0; v < num_vertices; v++) { subsets[v].parent = v; subsets[v].rank = 0; } int e = 0; int currentIndex = 0; int mstWeight = 0; int mstEdgesCount = 0; while (e < num_vertices - 1) { currentEdge[0].src = allEdges[currentIndex].src; currentEdge[0].dest = allEdges[currentIndex].dest; currentEdge[0].weight = allEdges[currentIndex].weight; int x = find(subsets, currentEdge[0].src); int y = find(subsets, currentEdge[0].dest); currentIndex++; if (x != y) { mstEdges[e].src = currentEdge[0].src; mstEdges[e].dest = currentEdge[0].dest; mstEdges[e].weight = currentEdge[0].weight; mstWeight += mstEdges[e].weight; mstEdgesCount++; if (mstEdges[e].weight == -1) { infEdgesTaken++; } e++; Union(subsets, x, y); } } free(subsets); //the kruskal algoritm itself - END //Restoring default weights for (int i = 0; i < num_edges; i++) { if (allEdges[i].weight == -1) { allEdges[i].weight += minimizedWeight+1; } } //Calculating built MST weight mstWeight += subtractedWeight/infEdgesTotal*infEdgesTaken; //an array to store all weight values in MST and a number of edges in MST with that weight weights_p myWeights = (weights_p)malloc(mstEdgesCount*sizeof(weights_t)); //a variable to store the number of different weight values in MST int num_weights = 0; //filling 'myWeights' array for(int i = 0; i < mstEdgesCount; i++) { myWeights[i].weight = -100; } for (int i = 0; i < mstEdgesCount; i++) { for (int j = 0; j < i + 1; j++) { if (myWeights[j].weight == -100) { myWeights[j].weight = mstEdges[i].weight; myWeights[j].occurCount = 1; num_weights++; break; } else if (myWeights[j].weight != mstEdges[i].weight){ continue; } else { myWeights[j].occurCount++; break; } } } free(currentEdge); //sorting all present weights by descending number of edges with that weight qsort(myWeights, num_weights, sizeof(weights_t), myComp2); //a variable to store a maximum number of weight occuriences in MST int mostOccs = myWeights[0].occurCount; free(myWeights); free(mstEdges); //adding info about current MST into 'myTrees' array myTrees[i].totalWeight = mstWeight; myTrees[i].mostOccurNumber = mostOccs; } // End of Krushkal Algorithm iteration free(weights); free(allEdges); //sorting 'myTrees' array to get an MST with maximum number of same-edge occuriences //and lowest weight in the top qsort(myTrees, newWeightIndex, sizeof(trees_t), myComp3); //outputing the result printf ("%d",myTrees[0].totalWeight); free(myTrees); system("pause"); return 0; } 

现在似乎有太多的循环，但说实话，我不知道如何更简化算法。

我真的需要一些关于如何提高此解决方案性能的建议。 可能有一些我看不到的显而易见的事情。

先感谢您！