通过值获取顶点

Question

我正在 Java.

中实现 Graph

Graph class 使用 LinkedList 作为顶点。并且每个顶点还包含LinkedList个相邻顶点。

我还在研究我的方法。我只需要快速说明一下接受 String 标签的 getVertex() 方法和 return 匹配该标签的 Vertex。

public class Graph
{
    private class Vertex
    {
        private String label;
        private LinkedList links; 
        private boolean visited; 
        
        Vertex(String label)
        {
            this.label = label; 
            LinkedList links = new LinkedList(); 
            visited = false; 
        }

        private void addEdge(Vertex vertex)
        {
            links.insertLast(vertex); 
        }

        private String getLabel()
        {
            return label; 
        }

        private LinkedList getAdjacent()
        {
            return links; 
        }

        private boolean isVisited()
        {
            return visited; 
        }

        private void visit()
        {
            visited = true; 
        }
 
        private void unvisit()
        {
            visited = false; 
        }
    }

    /* Classfields for Graph Class */   
    private LinkedList vertices; //Linked List for the vertices in the graph
    private int vCount; 
    private int eCount; 

    public Graph()
    { 
        LinkedList vertices = new LinkedList(); 
        vCount = 0; 
        eCount = 0; 
    } 

    public void addVertex(String label)
    {
        Vertex newVertex = new Vertex(label); 
        vertices.insertLast(newVertex);
        vCount++; 
    }

    public int getVertexCount()
    {
        return vCount; 
    }

    public Vertex getVertex(String label)
    {
        // what to return? 
    }

它应该很简单，但我不明白我将如何导入这个标签但是 return 一个 Vertex，与一个 LinkedList 一起工作。非常感谢任何提示！

Answer 1

如果你正在对一个作业进行赋值，你应该使用 LinkedList 那很好，但它是最好的集合选择，它可以作为图中所有顶点的存储，也可以作为顶点的邻接表

我建议您解决这些问题：

首先，不要使用行类型 LinkedList links，你应该总是指定一个泛型类型参数List<Vertex>.
针对接口而不是实现编写代码。 IE。使用 List<Vertex> 而不是 LinkedList<Vertex>。它使您的代码更加灵活。
为了能够通过 label 检索特定的 vertex，您可以使用 Map<String, Vertex> 来存储所有图的顶点。这样 getVertex() 的时间复杂度将减少到恒定时间，这比遍历列表要快得多。代码是单行 vertexByLabel.get(label).
维护一个保存顶点数的变量是多余的，因为您可以检查顶点集合的大小来获得这个值。
ArrayList 比 LinkedList 执行并具有更好的内存消耗。出于这个原因，它被认为是 List 接口的通用实现，如果您不希望在遍历时通过 Iterator 删除元素这样的用例，它是一个首选列表（这将在恒定时间内完成，这里 LinkedList 真的很闪耀）。此外，HashSet 可能在收集 相邻顶点 的角色中很有用，因为它会确保没有重复。

所以关于 getVertex() 方法，如果您同意使用地图的建议，代码将如下所示：

private Map<String, Vertex> vertexByLabel = new HashMap<>(); // it is advisable to initialise collections, if you are not passing argument with collection that holds values to the constructor, but just assigning a new collection

public Vertex getVertex(String label) {
   return vertexByLabel.get(label);
}

我还建议您对方法 addVertex() 和 addEdge() 进行更改。首先，我宁愿期望在 Vertex class 中有一个名为 addVertex() 的方法（我们正在向 this 顶点的邻接列表中添加一个新顶点）和一个方法 addEdge() 在 Graph 内（我们在图中连接个顶点）。

并且如果为了连接图的顶点方法 addEdge() 将期望顶点标签作为其第一个参数，并且相邻顶点的标签作为 variable arity argument (可变参数).

以防万一您有强烈的要求只使用 LinkedLinked 并且不允许使用通用类型。但坦率地说，禁止学生使用泛型似乎不是一个好主意。它并没有降低很多复杂性，因为您必须手动处理 down-casts，这是一个非常糟糕的做法。

您的方法可能如下所示：

public Vertex getVertex(String label) {
    Vertex result = null;
    for (Object next: vertices) { // all elements in the collection of row type a treated by the compiler as being of type Object
        Vertex vertex = (Vertex) next; // you need to cast the element into the Vertex type in order to be able to access its field `label`
        if (vertex.label.equals(label)) {
            result = vertex;
            break;
        }
    }
    return result;
}

通过值获取顶点

Getting a Vertex by its Value

java

algorithm

graph

linked-list

list