如何知道圖中是否存在頂點？

我正在製作一個從文件加載圖形的方法。這非常簡單，但如果有重複的頂點，該方法也會插入到圖中，所以我試圖避免這種情況。如何知道圖中是否存在頂點？

這是我當前的代碼：

public static Graph<ElementoDecorado<Integer>, String> loadGraphFromFile(File f) { 
     boolean v1_exists = false, v2_exists = false; 
     Graph<ElementoDecorado<Integer>, String> g = new AdjacencyListGraph<ElementoDecorado<Integer>, String>(); 
     Vertex<ElementoDecorado<Integer>> v1, v2, aux = null; 
     Scanner fr; 

     try { 
      fr = new Scanner(f); 

      while(fr.hasNextLine()) { 
       v1 = g.insertVertex(new ElementoDecorado<Integer>(fr.nextInt())); 
       v2 = g.insertVertex(new ElementoDecorado<Integer>(fr.nextInt())); 

       for(Vertex<ElementoDecorado<Integer>> v : g.vertices()) { 
        if(v.equals(v1)) { 

         /*aux = v; 
         v1_exists = true;*/ 
        } 
        if(v.equals(v2)) { 
         /*aux = v; 
         v2_exists = true;*/ 
        } 
       } 

       g.insertEdge(v1, v2, "edge"); 

       v1_exists = v2_exists = false; 
      } 
     } catch(FileNotFoundException e) { 
      e.printStackTrace(); 
     } 

     return g; 
    }

我不知道寫什麼到兩個IFS。我試圖刪除頂點，如果他們是平等的，但顯然這是行不通的，因爲最後我的圖將是空的：S

This is the manual page爲頂點接口。

任何幫助，歡迎。謝謝，聖誕快樂！

來源

2011-12-27 Puyover

的文檔是非常差的，但它是'graph.insertEdge（ v1，v2，o）'如果需要，應該添加頂點。該文件沒有提到實際發生的事情。 – toto2

我想圖表可以有許多具有相同整數的頂點。但是你想限制每個整數的單個頂點。 – toto2

這可能是首先要檢查的問題，找出它是否是這樣。 –

你應該先檢查一下graph.insertVertex(V value)是做什麼的。如果軟件包構建得體面（我從窮文檔中懷疑），那麼如果頂點value尚不存在，那麼該方法將只創建一個新頂點;否則返回值爲value的現有頂點。

但是，我無法從非文檔中知道包是否真的假定給定值有單個頂點，以及insertVertex行爲是否正確。

這裏是萬一insertVertex一些代碼不檢查重複：

（我換成ElementoDecorado<Integer>通過Integer的可讀性）

while(fr.hasNextLine()) { 
    int nodeId1 = fr.nextInt(); 
    int nodeId2 = fr.nextInt(); 
    Vertex<Integer> vert1 = null; 
    Vertex<Integer> vert2 = null; 

    for(Vertex<Integer> v : g.vertices()) { 
     int nodeId = v.element(); 
     if(nodeId == nodeId1) 
     vert1 = v; 
     else if (nodeId == nodeId2) // assumes can't have nodeId1 == nodeId2 
     vert2 = v; 
    } 
    if (vert1 == null) 
     vert1 = g.insertVertex(nodeId1); 
    if (vert2 == null) 
     vert2 = g.insertVertex(nodeId2); 

    g.insertEdge(vert1, vert2, null); 
}

來源

2011-12-27 19:03:56 toto2

+1，很高興有人完成了正確的解決方案。 –

是的！那工作得很好。謝謝！ – Puyover

在圖中插入頂點之前，詢問給定的頂點鍵是否已存在String值。

vertex = new ElementoDecorado<Integer>(fr.nextInt()); 
if(graph.get(key) != null) { 
    //it exists, don't insert it 
} else { 
    g.insertVertex(vertex) 
}

瞭解您自己的數據結構。問問自己，圖形是由什麼組成的？這只是一個映射：

ElementoDecorado<Integer> => String

還沒有命名的變量之類的東西：g。它沒有傳達任何意義。

來源

2011-12-27 18:32:21

我在'Graph'中看不到'get'方法，我錯過了什麼嗎？ –

看起來這是一張地圖，但你說得對，弗朗西斯，我想我可能已經跳過了槍。 –

問題是，你正在添加頂點到圖之前你檢查是否需要添加它們。第一，而不是直接將兩個頂點，只是閱讀：

v1 = new ElementoDecorado<Integer>(fr.nextInt()); 
v2 = new ElementoDecorado<Integer>(fr.nextInt());

然後，在for，你檢查頂點是否存在，就像你正在努力。你if小號看起來是這樣的：

if(!v1_exists && v.equals(v1)) { 
    v1 = v; 
    v1_exists = true; 
}

，類似的還有v2。最後，當且僅當v1_exists是假的，你加了頂點：

// right anfter the for-each 
if (!v1_exists) { 
    g.addVertex(v1); 
} 
if (!v1_exists) { 
    g.addVertex(v2); 
} 

g.insertEdge(v1, v2, "edge"); 
// etc

有一些優化，你也可以做，比如停止for當兩個頂點被發現，但應該這樣做。

請注意，這可能是一個更好的方法，但我不知道這些類。

來源

2011-12-27 18:34:18 Darkhogg

如何知道圖中是否存在頂點？

回答

相關問題