これが私がやろうとしていることです。cost[] node1[] と node2[] の 3 つの配列があります。これらの全体は、node1[i]、node2[i]、および cost[i] を持つグラフのエッジに対応し、頂点 node1[i] から node2[i] にエッジの重みが cost[i] であるエッジがあることを指定します。 .
これらのエッジを重みに関して並べ替えようとしています。つまり、マージソートを使用して cost[] 配列を並べ替えます。ただし、cost[] 配列のエントリを変更するときはいつでも、グラフのノードも変更する必要があるため、node1 および node2 配列の対応するエントリも変更したいと考えています。つまり、node1[]=1,2,3 および node2[]=2,3,1 cost[]={7 4 8} の場合、コスト配列をソートした後、node1 と node2 は node1[]=2,1 のようになります。 ,3 node2[]=3,2,1. コスト[]=4,7,8
これが私のコードです。
#include<stdio.h>
#include<stdlib.h>
int merge_sort(int arr[],int low,int high,int node1[],int node2[])
{
int mid;
if(low<high) {
mid=(low+high)/2;
// Divide and Conquer
merge_sort(arr,low,mid,node1,node2);
merge_sort(arr,mid+1,high,node1,node2);
// Combine
merge(arr,low,mid,high,node1,node2);
}
return 0;
}
int merge(int arr[],int l,int m,int h,int node1[],int node2[])
{
int arr1[80000],arr2[80000]; // Two temporary arrays to
int arr3[70000],arr4[70000];
int arr5[70000],arr6[70000];
int n1,n2,i,j,k;
n1=m-l+1;
n2=h-m;
for(i=0; i<n1; i++)
{
arr1[i]=arr[l+i];
arr3[i]=node1[l+i];
arr5[i]=node2[l+i];
}
for(j=0; j<n2; j++)
{
arr2[j]=arr[m+j+1];
arr4[i]=node1[m+j+1];
arr6[i]=node2[m+j+1];
}
arr1[i]=99999; // To mark the end of each temporary array
arr2[j]=99999;
arr3[i]=99999;
arr4[j]=99999;
arr5[i]=99999;
arr6[j]=99999;
i=0;
j=0;
for(k=l; k<=h; k++) { //process of combining two sorted arrays
if(arr1[i]<=arr2[j])
{
arr[k]=arr1[i++];
//node1[k]=arr3[i++]; COMMENTED LINES!!!!!!!!!!!
//node2[k]=arr5[i++];
}
else
{
arr[k]=arr2[j++];
//node1[k]=arr4[j++]; COMMENTED LINES!!!!!!!!~!
//node2[k]=arr6[j++];
}
}
return(0);
}
int main(void)
{
int i,j,n,vert1,vert2,weight;
scanf("%d",&n);
int adjmat[n+1][n+1],cluster[n+1][n+1];
int *cost,*node1,*node2;
node1=malloc(sizeof(int)*1000000);
node2=malloc(sizeof(int)*1000000);
cost=malloc(sizeof(int)*1000000);
for(i=0;i<n+1;i++)
for(j=0;j<n+1;j++)
{
adjmat[i][j]=0;
cluster[i][j]=0;
}
for(i=1;i<n+1;i++)
cluster[i][0]=i;
for(i=1;i<(n+1)*(n+1);i++)
{
scanf("%d %d %d",&vert1,&vert2,&weight);
node1[i]=vert1;
node2[i]=vert2;
cost[i]=weight;
if(node1[i]==node1[i-1] && node2[i]==node2[i-1] && cost[i]==cost[i-1])
break;
// printf("%d %d %d\n",node1[i],node2[i],cost[i]);
adjmat[vert1][vert2]=weight;
adjmat[vert2][vert1]=weight;
}
printf("\n%d\n",i);
merge_sort(cost,1,124751,node1,node2);
for(j=1;j<i;j++)
printf("%d %d %d\n",node1[j],node2[j],cost[j]);
return(0);
}
マージ関数の行にコメントを付けるたびに、コードはコスト配列をソートします。ただし、これらの行のコメントを外すと、何らかの形ですべてが 0 に等しくなります。つまり、node1 node2 と cost 配列のすべての整数が 0 になります。なぜこれが起こっているのか教えてもらえますか? ありがとう！