我采访了三星。我是一名应届毕业生,他们要求我编写一个应用程序:
- 这是一个城市图,每个城市都可以到达另一个城市(所有顶点可以相互到达),如果你移动(删除)有一些顶点它们会影响图(它会被分割并且一些顶点会永远不会互相联系)
问题是,确定顶点,如果它们被删除,它将断开图形(影响一个或多个顶点到达所有其他顶点)。
*不使用任何数据结构(没有队列,没有数组列表)只允许数组。
输入是这样的:
V = 顶点数。 E = 边数
输入文件中的边是这样的
1 2 3 4 3 6 4 8
1-2 是 1 和 2 之间的 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 对象的顶点数组中对该顶点的引用。
一个更概念化的解决方案可能是提供具有开始和结束顶点的二类边。
也许这对你有点帮助。
关于没有数据结构的 Java Graph 实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37002911/