0

グラフ理論のトピックから次のコードがあります。最小スパニングツリーのクラスカルアルゴリズム

#include<iostream>
#include<stdlib.h>
using namespace std;
int cost[10][10],i,j,k,n,m,c,visit,visited[10],l,v,count,count1,vst,p;
int main(){
    int dup1,dup2;
    cout<<" enter number of vertices "<<endl;
    cin>>n;
    cout<<"enter number of edges "<<endl;
    cin>>m;
    cout<<" EDGES  Cost "<<endl;
    for(k=1;k<=m;k++){
        cin>>i>>j>>c;
        cost[i][j]=c;
        cost[j][i]=c;

    }
    for(i=1;i<=n;i++)

        for(j=1;j<=m;j++)

            if(cost[i][j]==0)
                cost[i][j]=31999;
            visit=1;
            while(visit<n){
                v=31999;
                for(i=1;i<=n;i++)
                    for(j=1;j<=n;j++)
    if(cost[i][j]!=31999 && cost[i][j]<v && cost[i][j]!=-1)
    {
        int count=0;
        for(p=1;p<=n;p++){


            if(visited[p]==i || visited[p]==j)
                count++;
        }
        if(count>=2){

            for(p=1;p<=n;p++)
                if(cost[i][p]!=31999 && p!=j)
                    dup1=p;
             for(p=1;p<=n;p++)
                 if(cost[j][p]!=31999 && p!=i)
                     dup2=p;
            if(cost[dup1][dup2]==-1)
                continue;
        }
         l=i;
         k=j;
         v=cost[i][j];

        }

        cout<<" edgde from "<<l<<" --> "<<k;
        cost[l][k]=-1;
        cost[k][l]=-1;
        visit++;
        int count=0;
        count1=0;
        for(i=1;i<=n;i++)
        {

            if(visited[i]==1)
                count++;
            if(visited[i]==k)
                count1++;

        }
        if(count==0)
            visited[++vst]=1;
         if(count1==0)
             visited[++vst]=k;

        }


return 0;
}

これは機能し、次の入力に使用します 

1 2 1
2 3 2
3 4 3
1 3 3

ここで、頂点の数とエッジの数は4で、次のように出力されます。

edge from 1–&gt;2edge from 2–&gt;3edge from 1–&gt;3

私の質問は、意味上のエラーがありますか？また、配列と多くの変数を使用しましたが、このコードをショートさせることはできますか？私の（プログラミング）言語はc++です

4

1 に答える 1

2

ユーザー入力はこのコードを簡単に破ることができます。ユーザーがnまたはmに10以上の値を指定した場合、配列の最後から実行される可能性があります。

于 2011-11-02T10:06:04.060 に答える