没有数据结构的 Java Graph 实现

Question

我采访了三星。我是一名应届毕业生，他们要求我编写一个应用程序:

• 这是一个城市图，每个城市都可以到达另一个城市(所有顶点可以相互到达)，如果你移动(删除)有一些顶点它们会影响图(它会被分割并且一些顶点会永远不会互相联系)

问题是，确定顶点，如果它们被删除，它将断开图形(影响一个或多个顶点到达所有其他顶点)。

*不使用任何数据结构(没有队列，没有数组列表)只允许数组。

输入是这样的:

V = 顶点数。E = 边数

输入文件中的边是这样的

1 2 3 4 3 6 4 8

1-2 是 1 和 2 之间的 1 关系，它是双向的。

这个问题怎么解，你觉得对一个应届生来说难吗？

Answer 1

您可以定义一个类顶点(或节点)并将两个顶点之间的边映射为两个实例之间的关联。这可能有点天真，但如果您只设置简单的操作(如删除)，则可以工作。

public class Vertex {

    int number;
    Vertex[] vertices; // you have to look yourself if array is big enough

}

现在，每个顶点都有一个他连接到的顶点数组。如果在这个顶点数组中添加一个顶点，然后将调用顶点添加到添加顶点的数组中，就可以实现双向:

vertex.add(new Vertex(1)); //internally, it will be looked if array is big enoguh and then the add method will do its work

...

public void add(Vertex v) {
    //add into vertices
    ...
    v.add(this);
}

要删除一个顶点，删除操作应该删除其他 Vertices 对象的顶点数组中对该顶点的引用。

一个更概念化的解决方案可能是提供具有开始和结束顶点的二类边。

也许这对你有点帮助。