그래프의 Kruskal 함수에서 동적 데이터를 사용하여 qsort를 구현하는 방법

Question

그래프에서 가장 작은 경로를 찾을 수 있도록 Kruskal 함수를 만들었습니다. 하지만 버블 정렬을 사용하여 그것을 qscort를 사용하여 작동하도록 만들고 구조체를 동적으로 만들려고 노력 중이므로 더 효율적으로 사용할 수 있습니다.

사용되는 모든 기능이 작동하지만 의심 스러우면 나에게 요청하여 게시 할 수 있습니다. 나는 연합을 사용하여 pd(dynamcc partition)을 찾을 수 있습니다.

내 코드는 다음과 같습니다

struct _temp{ 
    float weight; 
    int source; 
    int destination; 
}; 
typedef struct _temp Temp; 

struct _graph{ 

    int NumberVertex; 
    int NumberEdges; 
    float* NeighborMatrix; 
}; 
typedef struct _graph Graph; 


struct din_part{ 
    int n; 
    int*v; 
}; 
typedef struct din_part PartDin; 


Graph* grKruskal(Graph* g) 
{ 
    Graph* tree_min = graph_Create(g->NumberVertex); 
    PartDin* p = pd_Create(g->NumberVertex); 
    int i, j,number_edges=0,n=0,representative; 
    Temp edges[300],temp; 

    for (i = 0; i < (g->NumberVertex); i++) 
    { 
     for (j = n; j < (g->NumberVertex); j++) 
     { 
      if(g->NeighborMatrix[g->NumberVertex * i + j]!=0) 
      { 
       edges[number_edges].weight=g->NeighborMatrix[g->NumberVertex * i + j]; 
       edges[number_edges].source=i; 
       edges[number_edges].destination=j; 
       number_edges++; 
      } 
     } 
     n++; 
    } 

    if(number_edges>0){ 
     for(i=0; i<number_edges; i++) 
     { 
      int change=0; 
      for(j=0 ;j<number_edges-1; j++) 
      { 
       if(edges[j].weight >edges[j+1].weight){  // blubble_sort 
        temp=edges[j]; 
        edges[j]= edges[j+1]; 
        edges[j+1]=temp; 
        change=1; 

       } 
      } 
      if(!change) 
      { 
       for(i=0;i<number_edges;i++) 
       { 
        if(pd_Representative(p,edges[i].source)!=pd_Representative(p,edges[i].destination)) 
        { 
         representative=pd_Union(p,edges[i].source,edges[i].destination); 
         graph_InsertEdge(arvore_min,edges[i].source,edges[i].destination,edges[i].weight); 
        } 
       } 
       p=pd_Free (p); 
       return tree_min; 

      } 
     } 
    } 
} 

Answer 1

당신은 <stdlib.h>에서 사용할 수있는 qsort 기능을 쉽게 C에서 퀵을 사용할 수 있습니다. 데이터 구조가 동적 일 필요는 없지만 프로그램의 유연성을 높이는 데 도움이됩니다.

그것의 서명은 다음

void qsort (void * base, size_t num, size_t size, int (* comparator) (const void *, const void *)); 

base는 정렬 할 벡터입니다.

num은 벡터의 요소 수입니다.

size은 sizeof에서 반환 된 각 요소의 크기입니다.

comparator은 두 개의 void 포인터를 수신하고 int을 반환하는 함수 포인터입니다. 이 함수는 첫 번째 인수가 두 번째 인수보다 크면 양수를 반환하고 그렇지 않으면 음수를 반환하고 양수인 경우 0을 반환해야합니다. 귀하의 경우에는

, 당신은 단순히

qsort((void*)edges, number_edges, sizeof edges[0], comparator); 

으로 거품 정렬 부품을 교체 그리고 그것은 당신의 구조체 동적으로 만들 것은 무엇을 의미 하는가 comparator

int edge_comparator(void *ptr1, void *ptr2){ 
    Temp edge1 = *((Temp *)ptr1); 
    Temp edge2 = *((Temp *)ptr2); 
    return edge1.weight - edge2.weight; 
}