從鄰接矩陣中刪除頂點的好方法

我正在爲我參加的算法課程編寫一個小型圖庫。從鄰接矩陣中刪除頂點的好方法

我已經實現了初始化圖，添加邊，添加頂點等基本操作。

現在我應該認識到頂點刪除。起初看起來很簡單，但當圖表由鄰接矩陣表示時，我找不到一個好方法來完成它。

我的想法是有代表在矩陣有效頂點，並定期調整的陣列和矩陣陣列，所以我寫了這個示例程序：

#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]; 
    } 
}

這是否是一個好主意？我能做什麼呢？由於

來源

2011-05-15 JustB

不回答你的問題，但也許你可以通過'DimSetVertices'對'DeactivateVertex（）'的引用，使變量反映更新的鄰接矩陣。也就是說，void DeactivateVertex（...，int * DimSetVertices）{... * DimSetVertices--; }' – ladaghini 2011-05-15 18:17:55

對不起，但'DimSetVertices'必須保持固定直到內存清理，因爲我使用它來在矩陣中找到正確的元素 – JustB 2011-05-15 18:25:38

交換頂點與陣列中的最後一個頂點被刪除。
更新矩陣符合。

來源

2011-06-06 14:54:21 palindrom

從鄰接矩陣中刪除頂點的好方法

回答

相關問題