我如何在 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;
    }
}

这是class边，由源节点和目的节点组成，成本以分钟表示。

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

这是 class 我想按分钟在优先级队列中排序的图表，排序将通过比较器界面完成。


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

您可能需要更改 Vertex 上的 getIndex() 方法。您正在查找字符串化字母表中 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 class 可以在添加边和顶点时执行此操作。首先，更改顶点构造函数以将其索引作为参数。然后，在图表中：

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

getVertex 方法用于获取或创建顶点，它确保它们都按照请求的顺序从 0 开始唯一命名和编号。

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

How could I give in Kruskal's algorithm the name of the locations (vertex) in the form of strings, more precisely city names?

java

algorithm

graph-algorithm