根据顶点的值获取顶点

Question

我正在实现一个图形在Java .

Graph类对顶点使用LinkedList。并且每个顶点还包含一个相邻顶点的LinkedList。

我还在研究我的方法。我只需要快速澄清getVertex()方法，该方法接受String标签并返回与该标签匹配的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? 
}

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

Answer 1

如果你正在进行赋值操作，并且你希望使用LinkedList，这很好，但它是集合的最佳选择，它可以作为图中所有顶点的存储，也可以作为顶点的邻接表

我建议你解决这些问题:

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

关于getVertex()方法，如果您同意使用map的建议，代码将看起来像这样:

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类中有一个名为addVertex()的方法(我们向this顶点的邻接表添加一个新顶点)和Graph中的方法addEdge()(我们在图中连接顶点)。

如果为了连接图的顶点方法addEdge()将期望一个顶点标签作为它的第一个参数，并且相邻顶点的标签作为可变密度参数(varargs)。

---

如果您强烈要求独占地使用LinkedLinked并且不允许使用泛型类型。但坦率地说，禁止学生使用仿制药似乎不是个好主意。它并没有大大降低复杂性，因为你必须处理手动向下转换，这是一个非常糟糕的做法。

你的方法可能是这样的:

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