プリムのアルゴリズムを実装しようとしています。次のようにファイルから入力を取得しています。
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");
}