我如何在 Kruskal 算法中以字符串的形式给出地点（顶点）的名称，更准确地说，是城市名称？

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;
    }
}

这是一个类Graph，我想按照优先级队列中的分钟数进行排序，排序将通过比较器接口完成。

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");
    }
}

}

主要是建立整个图，并使用2个方法，一个是用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);
    }

}

Answer 2

很多图算法都是使用密集编号的顶点来最有效地实现的。 如果你的源数据使用较长的键，那么你必须将它们映射到密集编号的索引上。

你的 Graph 类可以在添加边和顶点时做到这一点。 首先，改变你的顶点构造函数，将其索引作为参数。 然后，在Graph:

class Graph {
    ...

    final Map<String, Vertex> m_vertexMap = new HashMap<>();

    ...

    Vertex getVertex(String name) {
        final int nextIndex = m_vertexMap.size();
        return m_vertexMap.computeIfAbsent(name, n -> new Vertex(n, nextIndex));
    }

    ...
    void addEdge(String name1, String name2, int minutes) {
        Edge tmp = new Edge(getVertex(name1), getVertex(name2), minutes);
        edges.add(tmp);
    }
}

中，在Graph: The getVertex 方法用于获取或创建顶点，它确保这些顶点都是唯一命名，并按照请求的顺序从0开始编号。