85

我目前正在遵循 Steve Yegge 关于准备技术编程面试的建议： http: //steve-yegge.blogspot.com/2008/03/get-that-job-at-google.html

在他关于图表的部分中，他说：

在内存中表示图有三种基本方法（对象和指针、矩阵和邻接表），您应该熟悉每种表示形式及其优缺点。

CLRS 中描述了矩阵和邻接表表示的优缺点，但我无法找到将这些与对象表示进行比较的资源。

只是通过思考，我可以自己推断出一些，但我想确保我没有错过一些重要的事情。如果有人可以全面地描述这一点，或者向我指出这样做的资源，我将不胜感激。

4

4 回答 4

98

对象和指针

这些只是 hammar 在另一个答案中所说的基本数据结构，Java您可以用边和顶点等类来表示它。例如，一条边连接两个顶点，可以是有向的或无向的，它可以包含一个权重。一个顶点可以有一个 ID、名称等。大多数情况下，它们都有额外的属性。所以你可以用它们来构建你的图表，比如

Vertex a = new Vertex(1);
Vertex b = new Vertex(2);
Edge edge = new Edge(a,b, 30); // init an edge between ab and be with weight 30

这种方法通常用于面向对象的实现，因为它对于面向对象的用户来说更具可读性和方便性；）。

矩阵

矩阵只是一个简单的二维数组。假设您有可以表示为 int 数组的顶点 ID，如下所示：

int[][] adjacencyMatrix = new int[SIZE][SIZE]; // SIZE is the number of vertices in our graph
adjacencyMatrix[0][1] = 30; // sets the weight of a vertex 0 that is adjacent to vertex 1

这通常用于需要索引访问的密集图。你可以用它来表示一个无向/有向和加权的结构。

邻接表

这只是一个简单的数据结构组合，我通常使用HashMap<Vertex, List<Vertex>>. 类似使用的可以是HashMultimapGuava 中的。

这种方法很酷，因为您有 O(1)（摊销）顶点查找，它会返回我要求的这个特定顶点的所有相邻顶点的列表。

ArrayList<Vertex> list = new ArrayList<>();
list.add(new Vertex(2));
list.add(new Vertex(3));
map.put(new Vertex(1), list); // vertex 1 is adjacent to 2 and 3

这用于表示稀疏图，如果你在谷歌申请，你应该知道 webgraph 是稀疏的。您可以使用BigTable以更具可扩展性的方式处理它们。

哦，顺便说一句，这是这篇文章的一个很好的总结，里面有精美的图片；）

于 2011-05-04T17:23:39.310 回答
7

对象和指针大多与邻接表相同，至少为了比较使用这些表示的算法。

相比

struct Node {
    Node *neighbours[];
};

和

struct Node {
    Node *left;
    Node *right;
};

在后一种情况下，如果它比命名指针更容易使用，您可以轻松地即时构建邻居列表。

于 2011-05-04T15:57:23.490 回答
4

对象表示（关联列表）的优点是两个相邻顶点共享相同的边实例。这使得使用无向边数据（长度、成本、流量甚至方向）进行操作变得很容易。但是，它为指针使用了额外的内存。

于 2011-06-18T13:44:38.687 回答
3

另一个好资源：可汗学院 - “表示图”

除了邻接表和邻接矩阵之外，他们还将“边表”列为第三种图形表示。边缘列表可以解释为“边缘对象”的列表，就像托马斯的“对象和指针”答案中的那些。

优点：我们可以存储更多关于边缘的信息（Michal 提到）

缺点：这是一个非常慢的数据结构：

  • 查找一条边：O(log e)
  • 移除一条边：O(e)
  • 查找与给定节点相邻的所有节点：O(e)
  • 判断两个节点之间是否存在路径：O(e^2)

e = 边数

于 2018-02-24T06:38:14.063 回答