如何知道图中是否存在顶点？

Question

我正在制作一种从文件加载图表的方法。这很简单，但是如果有重复的顶点，该方法也会插入到图中，所以我试图避免这种情况。

这是我当前的代码：

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

我不知道在两个 if 中写入什么。我尝试删除顶点（如果它们相等），但显然这不起作用，因为最后我的图将是空的：S

这是 Vertex 接口的手册页。

欢迎任何帮助。 谢谢，圣诞快乐！

Answer 1

您应该首先检查 graph.insertVertex(V value) 的作用。如果包构建得体（我从糟糕的文档中对此表示怀疑），那么只有在具有 value 的顶点尚不存在时，该方法才会创建一个新顶点；否则它返回值value的现有顶点。

但是，我无法从非文档中判断该包是否确实假设给定值只有一个顶点以及 insertVertex 的行为是否正确。

以下是一些代码，以防 insertVertex 不检查重复：（

为了便于阅读，我将 ElementoDecorado 替换为 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);
 }

Answer 2

问题是您在检查是否需要添加顶点之前先将顶点添加到图表中。
首先，不要直接添加两个顶点，而是读取它们：

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 为 false 时，您才添加顶点：

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

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

您还可以进行一些优化，例如当两个顶点都为 false 时停止 for找到了，但这应该可以。

请注意，这可能是更好的方法，但我不知道这些课程。

Answer 3

在图中插入顶点之前，询问给定顶点键是否已有一个 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。它没有传达任何意义。