首页 文章

Java - 使用Adjacency列表实现的图的节点与Ints

提问于
浏览 次
2

我正在学习技术面试和图表对我来说很难 . 我很容易使用邻接矩阵，但与邻接列表的实现相混淆 .

问题是，我在网上看到的邻接列表的大部分实现（Example1，Example2和Example3）根本不使用节点 . 他们只使用一个整数的HashMap和LinkedLists . 这甚至是正确的吗？因为定义（Wikipedia）表示它由顶点或节点组成 . 此外，使用邻接矩阵的图的大多数实现使用节点而不是整数 . Example4 . 我错过了什么是这个难题？

我知道使用int而不是节点更节省空间，但是它会导致更多的复杂性 . 例如，查看example1中的这段代码 -

// add edge from vertices v1 to v2
void addEdge(int v1,int v2){
adj.get(v1).add(v2);
}

其目的是从v1到v2添加边 . 它完全忽略了可能存在多个具有相同int值的顶点的可能性，在这种情况下，它留下了方法addEdge（）可以在非预期顶点之间添加边缘的可能性 .

Example1,2,3中的Adjacency列表的实现是错误的吗？如果它们是正确的，如果我使用节点而不是整数实现邻接列表会不会很糟糕？我不希望我的采访者认为我是一个白痴大声笑

java graph nodes adjacency-list adjacency-matrix

1 回答

  • 0

    您可以使用Node（包含数据类型）或直接使用数据类型（在示例中为Integer），它们都可以工作

    然而，由于几个原因，使用Node是更好的选择

    • 避免使用重复数据值正确提到的问题

    • 使用节点更加面向对象 . 它允许Graph类使用Node保存的任何数据类型 . 这使得代码更具可移植性，因为图形可以使用String，Long，Integer等

    • 为了利用我上面提到的可移植性，应该像这样定义一个Node类

    class Node<T>{
    T data;
}

    因此，您应该始终在访谈中使用Node（包含数据类型），因为它看起来更好，并表明您关心设计正确的代码 .

    希望能帮助到你！

    回复于

相关问题