java - 我如何在克鲁斯卡尔算法中以字符串的形式给出位置(顶点)的名称，更准确地说是城市名称？

Question

我用 Kruskal 算法编写了以下代码，但我不知道如何修改它以使位置是城市名称。

public class Vertex {
    public char value;
    private char[] alphabet = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
    public Vertex(char val)
    {
        this.value = val;
    }
    public int getIndex()
    {
        int idx = new String(alphabet).indexOf(this.value);
        return idx;
    }
}

这是 Edge 类，由源节点和目标节点组成，成本以分钟为单位。

package com.utils;
import java.util.Comparator;

public class Edge {
    private Vertex source;
    private Vertex destination;
    private int minutes;

    public Edge(Vertex _source, Vertex _dest, int _min)
    {
        this.source = _source;
        this.destination = _dest;
        this.minutes = _min;
    }

    public Vertex getDestination() {
        return destination;
    }

    public Vertex getSource() {
        return source;
    }
    public int getMinutes() {
        return minutes;
    }

    @Override
    public String toString() {
        return "Source" + source + "-> Destination"+ destination + "Cost" + minutes;
    }
}

这是类图，我想按分钟在优先级队列中排序，排序将通过比较器接口(interface)完成。

import java.util.ArrayList;
import java.util.Comparator;
import java.util.Iterator;
import java.util.PriorityQueue;

public class Graph
{
    private int no_vertices;
    private int no_edges;
    private ArrayList<Edge> edges;
    private ArrayList<Edge> mst;


    public Graph(int vertices)
    {
        this.no_vertices = vertices;
        edges = new ArrayList<Edge>();
    }

    public void addEdges(Vertex sources, Vertex dest, int min)
    {
        Edge tmp = new Edge(sources, dest, min);
        edges.add(tmp);
        no_edges++;
    }
    public boolean isEmpty()
    {
        return edges.isEmpty();
    }

    public void computeKruskalMST()
    {
        PriorityQueue<Edge> pq = new PriorityQueue<Edge>(edges.size(), Comparator.comparingInt(comp -> comp.getMinutes()));

        for(int i = 0; i < edges.size(); i++)
        {
            pq.add(edges.get(i));
        }
        int []parent = new int[no_vertices];
        makeSet(parent);
        mst = new ArrayList<Edge>();

        while(!pq.isEmpty())
        {
            Edge edge = pq.remove();
             int x_set = find(parent, edge.getSource().getIndex());
            int y_set = find(parent, edge.getDestination().getIndex());

            if(x_set ==y_set)
            {

            }else{
                mst.add(edge);
                union(parent,x_set,y_set);
            }
        }
        System.out.println("Minimum Spanning Tree: ");

    }

    public void makeSet(int []parent)
    {
        for (int i = 0; i < no_vertices; i++)
        {
            parent[i] = i;
        }
    }

    public int find(int []parent, int vertex)
    {
        if(parent[vertex] != vertex)
            return find(parent, parent[vertex]);
        return vertex;
    }

    public void union(int []parent, int x, int y)
    {
        int x_set_parent = find(parent,x);
        int y_set_parent = find(parent,y);

        parent[y_set_parent] = x_set_parent;
    }

    public void printGraph()
{
    Iterator<Edge> it = mst.iterator();
    while (it.hasNext())
    {
        Edge temp = it.next();
        System.out.println("Start: " + temp.getSource().value + " --> FINISH: " + temp.getDestination().value + " == COST " + temp.getMinutes() + "min");
    }
}

}

主要是构建了整个图并使用了两种方法。一个负责 Kruskal 的最小生成树算法，另一个显示所需的结果。

public class Main {

    public static void main(String[] args) {
    int vertices =19;

        Graph graph = new Graph(vertices);
        graph.addEdges(new Vertex('A'), new Vertex('H'),1);
        graph.addEdges(new Vertex('E'), new Vertex('S'),1);
        graph.addEdges(new Vertex('B'), new Vertex('H'),2);
        graph.addEdges(new Vertex('F'), new Vertex('Q'),2);
        graph.addEdges(new Vertex('S'), new Vertex('Q'),3);
        graph.addEdges(new Vertex('D'), new Vertex('F'),3);
        graph.addEdges(new Vertex('B'), new Vertex('Q'),2);
        graph.addEdges(new Vertex('A'), new Vertex('E'),4);
        graph.addEdges(new Vertex('H'), new Vertex('S'),4);
        graph.addEdges(new Vertex('A'), new Vertex('S'),5);
        graph.addEdges(new Vertex('D'), new Vertex('E'),6);
        graph.addEdges(new Vertex('F'), new Vertex('S'),6);
        graph.addEdges(new Vertex('B'), new Vertex('S'),9);

       graph.computeKruskalMST();
       graph.printGraph();

    }
}

Answer 1

您可能需要更改您的getIndex()方法Vertex 。您正在查找 char value 的索引值在字符串化的字母表中。您需要将城市名称存储在 List<String> 中并使用.indexOf()在列表中。

public class Vertex {
    private static List<String> cityNames = Arrays.of("City1", "City2", "City3");  

    private String cityName;

    public Vertex(String cityName) { 
        this.cityName = cityName;
    }

    public int getIndex() {
        return cityNames.indexOf(this.cityName);
    }

}