1

プリムのアルゴリズムを実装しようとしています。次のようにファイルから入力を取得しています。

3 3   // Number of vertices and edges
1 2 3 // edge 1 edge 2 cost
2 3 4 // edge 2 edge 3 cost
1 3 4 // edge 1 edge 3 cost

次のようにコスト マトリックスを作成します。最初は、コスト マトリックスのすべての重みは無限大です (この場合は 9999)。

for(i = 0; i < n; i++)
{
    for( j = 0; j < n; j++)
    {
        cost[i][j] = 9999;
    }
}

ここで、ファイルから重みを読み取って、コスト マトリックスの重みを更新する必要があります。だから、私は次のようにファイルを読んでいます。

ifstream fin;
fin.open("input.txt",ios::in);
fin >> n; //nodes
fin >> e; //edges
while(fin)
{
    fin>>a>>b>>w;
    cost[a-1][b-1] =cost[b-1][a-1]= w;   
}
fin.close();

したがって、a と b はエッジで、w はそのエッジの重みです。したがって、edge(1,2) があり、その重みが 3 であるとします。したがって、コスト マトリックスは3cost[1][2]にcost[2][1]更新されるはずです。ファイル操作を使用してコスト マトリックスを更新する方法がわかりません。

もう一度言いますが、上記のファイルのようなテキスト ファイルがあります。ファイルの最初の行には、エッジの頂点の数が含まれています。変数 v の頂点と変数 e のエッジを読み取りたい。cost[i][i]次に、すべての値が無限大である初期コスト マトリックスがあります。このコスト マトリックスのエッジをファイルから更新したいと考えています。したがって、ファイルから 2 行目を読み取り、cost[1][2]= 3 を更新します。これを行う方法はまだわかりません。

これが私が今持っている完全なプログラムです：

#include<iostream>
#include<fstream>
using namespace std;

int n,e,a,b,w;
int **cost = new int*[n];

void prim()
{
int i,j,k,l,x,nr[10],temp,min_cost=0;
int **tree = new int*[n];

for(i = 0; i < n; i++)
tree[i]=new int[n];

/* For first smallest edge */
temp=cost[0][0];
for(i=0;i< n;i++)
 {
 for(j=0;j< n;j++)
 {
    if(temp>cost[i][j])
    {
    temp=cost[i][j];
    k=i;
    l=j;
    }
 }
}
/* Now we have fist smallest edge in graph */
tree[0][0]=k;
tree[0][1]=l;
tree[0][2]=temp;
min_cost=temp;

/* Now we have to find min dis of each 
vertex from either k or l
 by initialising nr[] array 
 */

 for(i=0;i< n;i++)
  {
   if(cost[i][k]< cost[i][l])
    nr[i]=k;
   else
    nr[i]=l;
   }
  /* To indicate visited vertex initialise nr[] for them to 100 */
  nr[k]=100;
  nr[l]=100;
  /* Now find out remaining n-2 edges */
  temp=99;
  for(i=1;i< n-1;i++)
   {
    for(j=0;j< n;j++)
     {
      if(nr[j]!=100 && cost[j][nr[j]] < temp)
       {
       temp=cost[j][nr[j]];
       x=j;
       }
   }
  /* Now i have got next vertex */
  tree[i][0]=x;
  tree[i][1]=nr[x];
  tree[i][2]=cost[x][nr[x]];
  min_cost=min_cost+cost[x][nr[x]];
  nr[x]=100;

   /* Now find if x is nearest to any vertex 
   than its previous near value */

for(j=0;j< n;j++)
{
if(nr[j]!=100 && cost[j][nr[j]] > cost[j][x])
     nr[j]=x;
}
temp=9999;
}
/* Now i have the answer, just going to print it */
cout<<"\n The minimum spanning tree is:"<<endl;
 for(i=0;i< n-1;i++)
{
for(j=0;j< 3;j++)
       cout<<tree[i][j];
cout<<endl;
}

 cout<<"\nMinimum cost:";
 cout<<min_cost;
}


 int main()
 {
  int i,j;

   for(i = 0; i < n; i++)
    cost[i]=new int[n];


for(i = 0; i < n; i++)
    {
    for( j = 0; j < n; j++)
        {
        cost[i][j] = 9999;
        }
    }

    ifstream fin;
     fin.open("input.txt",ios::in);

//cout<<n<<e;
     fin>>n>>e;

     while(fin>>a>>b>>w)
     {

    cost[a-1][b-1] = w;


      }
fin.close();
    prim();
    system("pause");
  }
4

1 に答える 1