6
I am carrying out the implementation of the algorithm of Christofides and input I receive the data from TSPLIB. Christofides' Algorithm has the following steps:
- Find the minimum generating tree
- Find all odd vertices (an even number of vertices)
- Find the perfect minimum marriage of the odd-degree vertices
- Add the edges of the perfect wedding at AGM
- Find an Eulerian path within that graph
I was doing the algorithm and I reached step 5, however, only then I realized that the marriage of the vertices I was meeting was not the perfect one, which is done in this code below:
int** adicionar_CM_na_AGM(int **m, int **agm, int qVgi, int *vGi,int n){
int menor =99999,v1=0,v2=0,verticeMenor;
int *aux = (int *) calloc(qVgi, sizeof(int));
for(int i=0; i<qVgi; i++)
{
for(int j=0; j<qVgi; j++)
{
if(vGi[i] != vGi[j] && menor > m[vGi[i]][vGi[j]] && aux[vGi[i]] != 1 && aux[vGi[j]] != 1)
{
printf("%d O %d\n", i, m[vGi[i]][vGi[j]]);
v1 = vGi[i];
v2 = vGi[j];
menor = m[vGi[i]][vGi[j]];
}
}
aux[v1]= 1;//cria a situação de já visitados
aux[v2]= 1;
agm[v1][v2] = m[v1][v2];//adiciona na AGM as arestas dos vGi
agm[v2][v1] = m[v2][v1];
menor =9999;
}
return agm;
where : m: adjacency matrix with vertex distances
agm: AGM adjacency matrix of m
qVgi: integer representing the amount of vertices of odd degree
vGi: vector containing vertex numbers that have odd degree
n: integer representing the total vertex number of the matrix m
I wonder if anyone would have ideas for me to find the perfect minimum marriage of the vertices of odd degree of my graph.
A tree does not by definition have vertices of odd degree necessarily? Its leaves?
– Jefferson Quesado
The tree only needs to be acyclic and connected, no?
– Rafael Paiva
Except for the root, the degree of every vertex is 1 + number of children. As leaves have no children, their degree is 1, therefore odd. I do not know the algorithm of Christofides, but it is that I found strange this selection of vertices of even degree.
– Jefferson Quesado
however, there may be degrees within the tree that are also odd, for example a degree attached to an even number of leaves, but my problem is actually a way to perfectly match the odd vertices and add edges between them, so I have a graph with an eulerian circuit.
– Rafael Paiva