1

グラフ上の最小パスを見つけることができるように、クラスカル関数を作成しました。しかし、私はバブルソートでそれを行いました。qsort を使用して動作させ、構造体を動的にして、より効率的にできるようにしようとしています。

使用されているすべての機能は機能していますが、疑問がある場合は私に尋ねて投稿できます. 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;

            }
        }
    }
}
4

1 に答える 1

0

qsortで利用可能な関数を使用して、C でクイックソートを簡単に使用できます<stdlib.h>。データ構造が動的である必要はありませんが、プログラムの柔軟性が向上します。

その署名は次のとおりです

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

baseソートしたいベクトルです。

numベクトルの要素数です。

sizeから返される各要素のサイズですsizeof。

comparatorvoidは、2 つのポインターを受け取って を返す関数への関数ポインターintです。この関数は、最初の引数が 2 番目の引数より大きい場合は正を返し、それ以外の場合は負を返し、等しい場合は 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;
 }
于 2012-06-16T17:14:25.790 に答える