1

入力に対してこのコードを実行できます。しかし、場合によっては、間違ったスパニング ツリーを取得します。例：プログラムの実行中に次のように入力した場合：

頂点の数を入力してください: 5 エッジの数を入力してください: 8

    Enter the vertices and the weight of edge 1:
    1
    3
    10

 Enter the vertices and the weight of edge 2:
1
4
100
 Enter the vertices and the weight of edge 3:
3
5
64
 Enter the vertices and the weight of edge 4:
1
2
13
 Enter the vertices and the weight of edge 5:
3
2
20
 Enter the vertices and the weight of edge 6:
2
5
5
 Enter the vertices and the weight of edge 7:
4
3
80
 Enter the vertices and the weight of edge 8:
4
5
40
MINIMUM SPANNING TREE :
2-5
1-3
4-5
MINIMUM COST = 55

expected o/p :

 MINIMUM SPANNING TREE :
    2-5
    1-3
    1-2
    4-5
    MINIMUM COST = 68

私の間違いを正すために親切に助けてください... plsは、私がコードで行った変更を教えてください.. plssss

コードは次のとおりです。

import java.io.*;  
class Edge
{
 int v1,v2,wt;   // wt is the weight of the edge
}
class kruskalsalgo
{
public static void main(String args[])throws IOException 
{ 
int i,j,mincost=0;
BufferedReader br=new BufferedReader( new InputStreamReader(System.in));
System.out.println(" Enter no.of vertices:");
int v=Integer.parseInt(br.readLine());
System.out.println(" Enter no.of edges:");
int e=Integer.parseInt(br.readLine());
 Edge ed[]=new Edge[e+1];
for(i=1;i<=e;i++)
{
 ed[i]=new Edge();
 System.out.println(" Enter the vertices and the weight of edge "+(i)+ ":"); 
 ed[i].v1=Integer.parseInt(br.readLine());
 ed[i].v2=Integer.parseInt(br.readLine());
 ed[i].wt=Integer.parseInt(br.readLine());
}
for(i=1;i<=e;i++)      // sorting the edges in ascending order
 for(j=1;j<=e-1;j++)
{
 if(ed[j].wt>ed[j+1].wt)
 {
   Edge t=new Edge();
    t=ed[j];
    ed[j]=ed[j+1];
    ed[j+1]=t;
}
}

int visited[]=new int[v+1];       // array to check whether the vertex is visited or not
for(i=1;i<=v;i++)
 visited[i]=0;
System.out.println("MINIMUM SPANNING TREE :");


for(i=1;i<=e;i++)
{ 
 if(i>v)
  break;
else if( visited[ed[i].v1]==0 || visited[ed[i].v2]==0)
 {
    System.out.println(ed[i].v1+ "-"+ ed[i].v2);
    visited[ed[i].v1]=visited[ed[i].v2]=1;
    mincost+=ed[i].wt;
 }
}
System.out.println("MINIMUM COST = " +mincost);
}
}
4

2 に答える 2

16

実際のアルゴリズムを参照する必要があります。http：//en.wikipedia.org/wiki/Kruskal%27s_algorithm コードにいくつかの間違いがあります。簡単にするために、

Edge class something like this:

class Edge implements Comparable<Edge>
{
    int v1,v2,wt; 

    Edge(int v1, int v2, int wt)
    {
        this.v1=v1;
        this.v2=v2;
        this.wt=wt;
    }

    @Override
    public int compareTo(Edge o) {
        Edge e1 = (Edge)o;
        if(e1.wt==this.wt)
            return 0;
        return e1.wt < this.wt ? 1 : -1;
    }

    @Override
    public String toString()
    {
        return String.format("Vertex1:%d \t Vertex2:%d \t Cost:%d\n", v1,v2,wt);

    }
}

ここでは、比較対象を拡張して、エッジでjava Collections.sort（）を使用できるようにします。これにより、昇順で並べ替えられ、toString（）がオーバーライドされるため、印刷やデバッグに使用できます。

訪問したアレイでは、ある時点で訪問したかどうかを確認するだけですが、それは最小スパニングツリーを作成するための基準ではありません。たとえば、入力でエッジ{1,2,5}、{2,5,5}、{4,5,40}を選択できます。これにより、すべての頂点に1回アクセスしますが、最小スパニングツリーは得られません。

アルゴリズムは最初に木の森を作るように言います。つまり、すべての頂点について、それ自体をメンバーとしてセットを作成する必要があります。このようなもの：

HashMap<Integer,Set<Integer>> forest = new HashMap<Integer,Set<Integer>>();
for(Integer vertex : vertices)
{
        //Each set stores the known vertices reachable from this vertex
        //initialize with it self.
    Set<Integer> vs = new HashSet<Integer>();
    vs.add(vertex);
    forest.put(vertex, vs);
}

次に、エッジを繰り返し処理します。スタックとして使用できるので、それらを並べ替えるとよいので、最小ツリーが見つかるか、エッジがなくなるまでポップします。エッジごとに、エッジによって結合されている2つの頂点の到達可能な頂点のセットをマージします。到達可能な頂点のセットが、エッジを構成する2つの頂点で同じである場合は、ループを形成するため、マージしないでください。そうでない場合は、最小ツリーにエッジを追加します。すべての頂点を含むセットを見つけたら、停止します。コードでは、次のようになります。

//sort your edges, you should use existing functionality where possible, saves testing needed
//here edges is your Stack, pop until minimum spanning tree is found.
Collections.sort(edges);
ArrayList<Edge> minSpanTree = new ArrayList<Edge>();
while(true) //while you haven't visited all the vertices at least once
{
    Edge check = edges.remove(0);//pop

    Set<Integer> visited1 = forest.get(check.v1);
    Set<Integer> visited2 = forest.get(check.v2);
    if(visited1.equals(visited2))
        continue;
    minSpanTree.add(check);
    visited1.addAll(visited2);
    for(Integer i : visited1)
    {
        forest.put(i, visited1);
    }
    if(visited1.size()==vertices.length)
        break;
}

したがって、次の入力の場合：

入力：[Vertex1：2 Vertex2：5コスト：5、Vertex1：1 Vertex2：3コスト：10、Vertex1：1 Vertex2：2コスト：13、Vertex1：3 Vertex2：2コスト：20、Vertex1：4 Vertex2：5コスト：40、Vertex1：3 Vertex2：5コスト：64、Vertex1：4 Vertex2：3コスト：80、Vertex1：1 Vertex2：4コスト：100]

最小全域木を取得します。出力：[Vertex1：2 Vertex2：5コスト：5、Vertex1：1 Vertex2：3コスト：10、Vertex1：1 Vertex2：2コスト：13、Vertex1：3 Vertex2：2コスト：20、 Vertex1：4 Vertex2：5コスト：40]

-ニル

于 2013-02-02T10:04:25.297 に答える