인접 행렬에서 꼭지점을 삭제하는 좋은 방법

Question

내가 참석중인 알고리즘 과정을위한 작은 그래프 라이브러리를 작성하고 있습니다.

그래프 초기화, 가장자리 추가, 정점 추가 등과 같은 기본 작업을 구현했습니다.

이제 정점 삭제를 실현해야합니다. 처음에는 단순 해 보였지만 그래프가 인접 행렬로 표시 될 때 좋은 방법을 찾을 수 없습니다.

내 생각은 배열 매트릭스의 활성 정점을 나타내는 주기적으로 배열과 행렬의 크기를 조정을하는 것입니다, 그래서 나는이 샘플 프로그램을 작성 :

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

이 좋은 생각이 있습니까를? 그렇지 않으면 무엇을 할 수 있습니까? 감사

Answer 1

• 스왑 정점은 배열의 마지막 정점으로 삭제 될 수 있습니다.
• 업데이트 매트릭스.