将对象图表示法与邻接表和矩阵表示法进行比较

Question

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

在他关于图形部分的介绍中，他指出:

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

CLRS详细描述了矩阵和邻接列表表示法的优缺点，但我还没有找到一些资源将这些与对象表示法进行比较。

单凭自己的想象力，我可以推断出一些东西，但我想确保自己没有漏掉重要的内容。如果有人能够全面地描述这个问题，或者指导我去某个能够解释清楚的资源，我将不胜感激。

- jbeard4

---

那么归纳图呢？它们属于这三个类别中的哪一个？ - Erik Kaplun

Answer 1

对象和指针

就像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>>来实现。类似的工具可以使用Guava中的HashMultimap。

这种方法很酷，因为您可以通过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

这个用于表示稀疏图，如果您正在申请Google公司，那么您应该知道WebGraph是稀疏的。您可以使用BigTable以更可扩展的方式处理它们。

另外顺便提一下，这里有一个非常好的摘要，带有漂亮的图片 ;)

- Thomas Jungblut

---

这种方法很酷，因为你可以在O(1)的时间内查找顶点。这个复杂度稍微有点不对，特别是它是O(1+alpha)，其中alpha = 哈希映射中的槽位数目 / 顶点数目。因此，我建议使用数组而不是哈希映射。 - Timofey

@Tim，我认为这里的每个人都知道数组访问比任何哈希表使用都要快。因此，没有必要在可以忽略的小常量 alpha 开销周围纠缠不清。 - Thomas Jungblut

请别误会，我并不是要冒犯你的好回答，但我有一种感觉，你的回答可能还有改进的空间，所以为什么不在这里提一下呢 :) - Timofey

@Tim，我已将摊销说明添加到答案中。谢谢。 - Thomas Jungblut

@ThomasJungblut，我发现你和Hammar对于“对象和指针”的描述有很大的不同。你正在创建一个新的Edge对象，而Hammar则是保留指向邻居的指针并给出明确的名称。但是你说：“这些只是像Hammar在另一个答案中所说的基本数据结构。” 你能不能再清楚一点？ - Md. Abu Nafee Ibna Zahid

Answer 2

对象和指针在大多数情况下与邻接表相同，至少用于比较使用这些表示法的算法。

比较

struct Node {
    Node *neighbours[];
};

使用

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

如果实时构建邻居列表比使用命名指针更容易处理，那么在后一种情况下可以轻松地动态构建邻居列表。

- hammar

Answer 3

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

- Michal Čizmazia

---

为什么与邻接表表示有关的链接被称为“关联表”？也许最好使用这个链接：http://www.algorithmist.com/index.php/Graph_data_structures#Incidence_List - Timofey

Answer 4

另一个好的资源：可汗学院 - "图的表示"

除了邻接表和邻接矩阵，它们列出了“边列表”作为第三种图形表示类型。边列表可以被解释为类似于Thomas“对象和指针”答案中的“边缘对象”的列表。

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

缺点：它是一种非常慢的数据结构：

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

e = 边数

- Chris Leung