2

参加しているアルゴリズムコース用の小さなグラフライブラリを作成しています。

グラフの初期化、エッジの追加、頂点の追加などの基本的な操作を実装しました。

ここで、頂点の削除を実現する必要があります。最初は単純に見えましたが、グラフが隣接行列で表されている場合、それを行うための良い方法を見つけることができません。

私の考えは、マトリックス内のアクティブな頂点を表す配列を作成し、配列とマトリックスのサイズを定期的に変更することです。そのため、次のサンプルプログラムを作成しました。

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#define DIM 4

void DeactivateVertex( int *Vertices, int DeactivatedVertex, int DimSetVertices );
void PrintMatrix( int *Mat, int *Vertices, int NumVertici, int DimSetVertices);

int main(void)
{
    int i, j;
    int *Mat = malloc( DIM * DIM * sizeof(int) );
    int *Vertices = malloc(DIM * sizeof(int) );
    int *TempVertici = NULL;
    int *TempMat = NULL;

    int NumVertici = DIM;
    int DimSetVertices = DIM;

    srand(time(NULL));

    //Initialize matrix with values from 1 to NumVertici
    for( i = 0; i < NumVertici * NumVertici; i++ )
    {
        Mat[i] = i+1;
    }
    //Initialize vertices set
    for( i = 0; i < NumVertici; i++ )
    {
        Vertices[i] = i;
    }
    /*
     * Vertices 
     * _0_1_2_3_ 
     * |0_1_2_3|
     *
     * Mat
     *  _0_1_2_3_
     * 0|1 2 3 4 
     * 1|5 6 7 8 
     * 2|9 10 11 12 
     * 3|13 14 15 16 
     *
     *
     * */
    PrintMatrix( Mat, Vertices, NumVertici, DimSetVertices );

    // "Delete" vertices 1 and 2
    DeactivateVertex( Vertices, 2, DimSetVertices );
    NumVertici--;
    DeactivateVertex( Vertices, 1, DimSetVertices );
    NumVertici--;
    /*
     * Vertices 
     * _0_1_2_3_ 
     * |0_3_ _ |
     *
     * Mat
     *  _0_1_2_3_
     * 0|1 2 3 4 
     * 1|5 6 7 8 
     * 2|9 10 11 12 
     * 3|13 14 15 16 
     */
    PrintMatrix( Mat, Vertices, NumVertici, DimSetVertices );

    //Memory cleanup: this will be done periodically
    printf("Memory Cleanup\n");

    TempMat = malloc( NumVertici * NumVertici * sizeof(int) );
    for( i = 0; i < NumVertici; i++ )
    {
        for( j = 0; j < NumVertici; j++ )
        {
            TempMat[i * NumVertici + j] = Mat[ Vertices[i] * DimSetVertices + Vertices[j] ];
        }
    }
    free( Mat );
    Mat = TempMat;
    TempMat = NULL;

    TempVertici = realloc( Vertices, NumVertici * sizeof(int) );
    if( TempVertici != NULL )
    {
        Vertices = TempVertici;
    }
    for( i = 0; i < NumVertici; i++ )
    {
        Vertices[i] = i;
    }
    TempVertici = NULL;
    DimSetVertices = NumVertici;
    /*
     * Vertices 
     * _0_1_ 
     * |0_1_|
     *
     * Mat
     *  _0__1_
     * 0|1  4 
     * 1|13 16 
     */

    PrintMatrix( Mat, Vertices, NumVertici, DimSetVertices );

    free( Mat );
    free( Vertices );
    return 0;
}   /* main */
/**
 * Mat => Puntatore alla matrice di adiacenza
 * Vertices => Array contenente gli indici dei vertici "attivi"
 * NumVertici => Numero di vertici attivi
 * DimSetVertices => Dimensione iniziale dell'insieme dei vertici
 * */
void PrintMatrix( int *Mat, int *Vertices, int NumVertici, int DimSetVertices)
{
    int i, j;

    for( i = 0; i < NumVertici; i++ )
    {
        for( j = 0; j < NumVertici; j++ )
        {
            printf( "%d ", Mat[ Vertices[i] * DimSetVertices + Vertices[j] ] );
        }
        printf("\n");
    }   
}

void DeactivateVertex( int *Vertices, int DeactivatedVertex, int DimSetVertices )
{
    int i;
    printf("Delete vertex %d\n", DeactivatedVertex);
    for( i = DeactivatedVertex; i < DimSetVertices-1; i++ )
    {
        Vertices[i] = Vertices[i+1];
    }
}

これは良い考えですか？それ以外に何ができますか？ありがとう

4

1 に答える 1

0
  • 削除する頂点を配列の最後の頂点と交換します。
  • それに応じてマトリックスを更新します。
于 2011-06-06T14:54:21.063 に答える