从邻接矩阵中删除顶点的好方法
||
我正在为参加的算法课程编写一个小型图形库。
我已经实现了一些基本操作，例如初始化图形，添加边线，添加顶点等。
现在我应该实现顶点删除。乍一看，这似乎很简单，但是当图形由邻接矩阵表示时，我找不到一种好的方法。
我的想法是要有一个表示矩阵中活动顶点的数组，并定期调整数组和矩阵的大小，因此我编写了以下示例程序：
#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];
}
}
没有找到相关结果
已邀请:
1 个回复
疼嘶桐