0

我正在尝试编写一个程序，该程序将使用 Kruskal 和 Prim 算法找到给定无向加权图的 MST。我已经在程序中成功地实现了 Kruskal 的算法，但是我遇到了 Prim 的问题。更准确地说，我不知道如何实际构建 Prim 函数，以便它遍历图中的所有顶点。我在程序执行期间遇到了一些 IndexOutOfBoundsException 错误。我不确定其他人需要多少信息才能了解我到目前为止所做的事情，但希望不会有太多无用的信息。

这是我到目前为止所拥有的：

我有一个Graph,Edge和一个Vertex类。

  • 顶点类大多只是一个包含顶点名称（编号）的信息存储。

  • Edge 类可以创建一个具有获取参数的新 Edge (Vertex start, Vertex end, int edgeWeight)。该类具有返回通常信息的方法，例如开始顶点、结束顶点和权重。

  • Graph 类从文本文件中读取数据并将新边添加到 ArrayList。文本文件还告诉我们图形有多少个顶点，并且也被存储了。

在Graph课堂上，我有一个 Prim() - 应该计算 MST 的方法：

    public ArrayList<Edge> Prim(Graph G) {

    ArrayList<Edge> edges = G.graph; // Copies the ArrayList with all edges in it.
    ArrayList<Edge> MST = new ArrayList<Edge>();

    Random rnd = new Random();

    Vertex startingVertex = edges.get(rnd.nextInt(G.returnVertexCount())).returnStartingVertex(); // This is just to randomize the starting vertex.

    // This is supposed to be the main loop to find the MST, but this is probably horribly wrong..
    while (MST.size() < returnVertexCount()) {

        Edge e = findClosestNeighbour(startingVertex);
        MST.add(e);
        visited.add(e.returnStartingVertex());
        visited.add(e.returnEndingVertex());
        edges.remove(e);

    }

    return MST;
}

findClosesNeighbour() 方法如下所示：

public Edge findClosestNeighbour(Vertex v) {

    ArrayList<Edge> neighbours = new ArrayList<Edge>();
    ArrayList<Edge> edges = graph;

    for (int i = 0; i < edges.size() -1; ++i) {

        if (edges.get(i).endPoint() == s.returnVertexID() && !visited(edges.get(i).returnEndingVertex())) {

            neighbours.add(edges.get(i));
        }
    }

    return neighbours.get(0); // This is the minimum weight edge in the list.
}

ArrayList<Vertex> visited并ArrayList<Edges> graph在创建新图形时构建。

Visited() - 方法只是一个布尔检查，看看 ArrayList 是否包含我们正在考虑移动到的顶点。我findClosestNeighbour()独立测试了它，它似乎正在工作，但如果有人发现它有问题，那么也欢迎反馈。

主要是正如我提到的，我的问题是在 Prim() 方法中实际构建主循环，如果需要任何其他信息，我很乐意提供。

谢谢你。

编辑：澄清我的 Prim() 方法的思路是什么。我想要做的是首先随机化图中的起点。之后，我会找到离该起点最近的邻居。然后我们将连接这两个点的边添加到 MST，并将顶点添加到访问列表中以供稍后检查，这样我们就不会在图中形成任何循环。

这是引发的错误：

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 0, Size: 0
    at java.util.ArrayList.rangeCheck(Unknown Source)
    at java.util.ArrayList.get(Unknown Source)
    at Graph.findClosestNeighbour(graph.java:203)
    at Graph.Prim(graph.java:179)
    at MST.main(MST.java:49)

第 203 行：return neighbour.get(0);在 findClosestNeighbour() 中

第 179 行：Edge e = findClosestNeighbour(startingVertex);在 Prim() 中

4

2 回答 2

0 
Vertex startingVertex = edges.get(rnd.nextInt(G.returnVertexCount())).returnStartingVertex();

这使用顶点计数来索引边列表，混合顶点和边。

// This is supposed to be the main loop to find the MST, but this is probably horribly wrong..
while (MST.size() < returnVertexCount()) {

    Edge e = findClosestNeighbour(startingVertex);
    MST.add(e);
    visited.add(e.returnStartingVertex());
    visited.add(e.returnEndingVertex());
    edges.remove(e);
}

这不应该每次都将相同的startingVertex 传递给findClosestNeighbour。

public Edge findClosestNeighbour(Vertex v) {

    ArrayList<Edge> neighbours = new ArrayList<Edge>();
    ArrayList<Edge> edges = graph;

    for (int i = 0; i < edges.size() -1; ++i) {

        if (edges.get(i).endPoint() == s.returnVertexID() && !visited(edges.get(i).returnEndingVertex())) {

            neighbours.add(edges.get(i));
        }
    }

    return neighbours.get(0); // This is the minimum weight edge in the list.
}

这是什么s？这看起来不像是在考虑边缘权重。它正在跳过最后一条边，并且仅在边无方向时检查结束顶点。

于 2012-03-31T23:26:55.497 回答
0 
// Simple weighted graph representation 
// Uses an Adjacency Linked Lists, suitable for sparse graphs /*undirected

9 A B C D E F G H I AB 1 BC 2 CE 7 EG 1 GH 8 FH 3 FD 4 DE 5 IF 9 IA 3 AD 1 这是我使用的图形保存为graph.txt */

import java.io.*;
import java.util.Scanner;

class Heap
{
    private int[] h;       // heap array
    private int[] hPos;    // hPos[h[k]] == k
    private int[] dist;    // dist[v] = priority of v
    private int MAX;

    private int N;         // heap size

    // The heap constructor gets passed from the Graph:
    //    1. maximum heap size
    //    2. reference to the dist[] array
    //    3. reference to the hPos[] array
    public Heap(int maxSize, int[] _dist, int[] _hPos) 
    {
        N = 0;
        MAX = maxSize;
        h = new int[maxSize + 1];
        dist = _dist;
        hPos = _hPos;
    }


    public boolean isEmpty() 
    {
        return N == 0;
    }


    public void siftUp( int k) 
    {
        int v = h[k];

        h[0] = 0;
        dist[0] = Integer.MIN_VALUE;

        //vertex using dist moved up heap
        while(dist[v] < dist[h[k/2]]){


            h[k] = h[k/2]; //parent vertex is assigned pos of child vertex

            hPos[h[k]] = k;//hpos modified for siftup

            k = k/2;// index of child assigned last parent to continue siftup
        }

        h[k] = v;//resting pos of vertex assigned to heap

        hPos[v] = k;//index of resting pos of vertex updated in hpos

        //display hpos array
       /* System.out.println("\nThe following is the hpos array after siftup: \n");

        for(int i = 0; i < MAX; i ++){

            System.out.println("%d", hPos[i]);
        }

        System.out.println("\n Following is heap array after siftup: \n");

        for (int i = 0; i < MAX; i ++ ){

            System.out.println("%d" , h[i]);

        }*/
    }


    //removing the vertex at top of heap
    //passed the index of the smallest value in heap
    //siftdown resizes and resorts heap

    public void siftDown( int k) 
    {
        int v, j;

        v = h[k];  

        while(k <= N/2){

            j = 2 * k;

            if(j < N && dist[h[j]] > dist[h[j + 1]]) ++j; //if node is > left increment j child

            if(dist[v] <= dist[h[j]]) break;//if sizeof parent vertex is less than child stop.

            h[k] = h[j];//if parent is greater than child then child assigned parent pos

            hPos[h[k]] = k;//update new pos of last child

            k = j;//assign vertex new pos
        }
        h[k] = v;//assign rest place of vertex to heap
        hPos[v] = k;//update pos of the vertex in hpos array
    }


    public void insert( int x) 
    {
        h[++N] = x;//assign new vertex to end of heap
        siftUp( N);//pass index at end of heap to siftup
    }


    public int remove() 
    {   
        int v = h[1];
        hPos[v] = 0; // v is no longer in heap
        h[N+1] = 0;  // put null node into empty spot

        h[1] = h[N--];//last node of heap moved to top
        siftDown(1);//pass index at top to siftdown

        return v;//return vertex at top of heap
    }

}

class Graph {
    class Node {
        public int vert;
        public int wgt;
        public Node next;
    }

    // V = number of vertices
    // E = number of edges
    // adj[] is the adjacency lists array
    private int V, E;
    private Node[] adj;
    private Node z;
    private int[] mst;

    // used for traversing graph
    private int[] visited;
    private int id;


    // default constructor
    public Graph(String graphFile)  throws IOException
    {
        int u, v;
        int e, wgt;
        Node t;

        FileReader fr = new FileReader(graphFile);
        BufferedReader reader = new BufferedReader(fr);

        String splits = " +";  // multiple whitespace as delimiter
        String line = reader.readLine();        
        String[] parts = line.split(splits);
        System.out.println("Parts[] = " + parts[0] + " " + parts[1]);

        V = Integer.parseInt(parts[0]);
        E = Integer.parseInt(parts[1]);

        // create sentinel node
        z = new Node(); 
        z.next = z;

        // create adjacency lists, initialised to sentinel node z       
        adj = new Node[V+1];        
        for(v = 1; v <= V; ++v)
            adj[v] = z;               

       // read the edges
        System.out.println("Reading edges from text file");
        for(e = 1; e <= E; ++e)
        {
            line = reader.readLine();
            parts = line.split(splits);
            u = Integer.parseInt(parts[0]);
            v = Integer.parseInt(parts[1]); 
            wgt = Integer.parseInt(parts[2]);

            System.out.println("Edge " + toChar(u) + "--(" + wgt + ")--" + toChar(v));    

            // write code to put edge into adjacency matrix 
            t = new Node(); t.vert = v; t.wgt = wgt; t.next = adj[u]; adj[u] = t;

            t = new Node(); t.vert = u; t.wgt = wgt; t.next = adj[v]; adj[v] = t;    

        }          
    }

    // convert vertex into char for pretty printing
    private char toChar(int u)
    {  
        return (char)(u + 64);
    }

    // method to display the graph representation
    public void display() {
        int v;
        Node n;

        for(v=1; v<=V; ++v){
            System.out.print("\nadj[" + toChar(v) + "] ->" );
            for(n = adj[v]; n != z; n = n.next) 
                System.out.print(" |" + toChar(n.vert) + " | " + n.wgt + "| ->");    
        }
        System.out.println("");
    }


    //use the breath first approach to add verts from the adj list to heap
    //uses 3 arrays where array = # of verts in graph
    //parent array to keep track of parent verts
    // a dist matrix to keep track of dist between it and parent
    //hpos array to track pos of vert in the heap

    public void MST_Prim(int s)
    {
        int v, u;
        int wgt, wgt_sum = 0;
        int[]  dist, parent, hPos;
        Node t;

        //declare 3 arrays
        dist = new int[V + 1];
        parent = new int[V + 1];
        hPos = new int[V +1];

        //initialise arrays
        for(v = 0; v <= V; ++v){

            dist[v] = Integer.MAX_VALUE;
            parent[v] = 0;
            hPos[v] = 0;
        }

        dist[s] = 0;

        //d.dequeue is pq.remove

        Heap pq =  new Heap(V, dist, hPos);
        pq.insert(s);

        while (! pq.isEmpty())  
        {
            // most of alg here
            v = pq.remove();
            wgt_sum += dist[v];//add the dist/wgt of vert removed to mean spanning tree

            //System.out.println("\nAdding to MST edge {0} -- ({1}) -- {2}", toChar(parent[v]), dist[v], toChar[v]);

            dist[v] = -dist[v];//mark it as done by making it negative

            for(t = adj[v]; t != z; t = t.next){

                u = t.vert;
                wgt = t.wgt;

                if(wgt < dist[u]){ //weight less than current value

                    dist[u] = wgt;
                    parent[u] = v;

                    if(hPos[u] == 0)// not in heap insert
                        pq.insert(u);
                    else
                        pq.siftUp(hPos[u]);//if already in heap siftup the modified heap node
                }
            }

        }
        System.out.print("\n\nWeight of MST = " + wgt_sum + "\n");

        //display hPos array
        /*System.out.println("\nhPos array after siftUp: \n");

        for(int i = 0; i < V; i ++){

            System.out.println("%d", hPos[i]);
        }*/

        mst = parent;                           
    }

    public void showMST()
    {
            System.out.print("\n\nMinimum Spanning tree parent array is:\n");
            for(int v = 1; v <= V; ++v)
                System.out.println(toChar(v) + " -> " + toChar(mst[v]));
            System.out.println("");
    }

}

public class PrimLists {
    public static void main(String[] args) throws IOException
    {
        int s = 2;
        String fname = "graph.txt";               

        Graph g = new Graph(fname);

        g.display();


    }


}
于 2017-05-04T17:54:45.040 回答