通過值獲取頂點

我正在用 Java 實作一個圖表。

該類Graph使用 aLinkedList作為頂點。并且每個頂點還包含一個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? 
    }

它應該很簡單，但我不明白我將如何匯入這個標簽但回傳 a Vertex，使用 a LinkedList。將不勝感激任何提示！

uj5u.com熱心網友回復：

如果您正在對分配進行分配，并且您應該使用LinkedList它很好，但它是集合的最佳選擇，它可以作為圖形中所有頂點的存盤，也可以作為頂點的鄰接串列

我建議你解決這些問題：

• 首先，不要使用行型別 LinkedList links，你應該總是指定一個泛型型別引數List<Vertex>。
• 針對介面撰寫代碼，而不是針對實作。即使用List<Vertex>而不是LinkedList<Vertex>. 它使您的代碼更加靈活。
• 為了能夠通過label檢索特定頂點，您可以使用 a來存盤圖形的所有頂點。隨著時間復雜度將降低到恒定時間，它比迭代串列要快得多。并且代碼是一行。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(). 首先，我寧愿期望addVertex()在類內部呼叫一個方法Vertex（我們正在向頂點的鄰接串列添加一個新頂點this）和一個addEdge()內部方法Graph（我們正在連接圖中的頂點）。

如果為了連接圖的頂點方法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;
}

標籤：爪哇 列表 算法 图形 链表

上一篇：在陣列中查找元素出現的位置

下一篇：data.frame和data.table中的order()