图形通常是如何定义的？

Question

图形通常是如何定义的？

4

我看到一个面试问题，其中图形结构被定义为:

struct Node{
   vector<Node*> neighbors;
}

我觉得这很不寻常，或者可能是一个错误，因为没有什么可以真正区分节点间的差异。我的推理正确吗，还是说一个图可以只用邻居向量来定义？我想我们必须像这样：

template<typename T>
struct Node{
   T value;
   vector<Node*> neighbors;
}

这对我来说更直观。

有没有什么“典型”的方法来定义图？例如，对于二叉树，我们至少需要一个值，加上左右指针。对于链表，我们至少需要一个值和一个下一个指针等。

- Bob John

图节点必须具有引用节点数据的某种方式，可以是指向数据结构的指针或在结构体内部。另一种表示方法是通过邻接矩阵，这对于稠密图可能很方便。 - Matt Coubrough

1

如果面试问题不需要 T value，则无需添加它（例如计算连通组分）。 - Jarod42

1

没有绝对的要求图节点包含数据，尽管这很常见。数据可以存储在图外部的表中（由节点指针键入），或者它可以是一个没有其他数据的结构。 - M.M

1

我在我的毕业论文中写了如何通用实现图算法，一直希望有人问这样的问题！我认为这将是一次有趣的经历。到目前为止，我只有两次机会在我的实际工作中使用实际的图算法（一次是相当原始的图搜索，但另一次实际上需要一个网络单纯形实现）。 - Dietmar Kühl

@DietmarKühl 你应该尝试游戏设计！那里需要大量的图形算法工作 :) - Bob John

@BobJohn：在游戏行业中，我从未认为薪水是最吸引人的一点 - 看起来金融行业的薪水要好得多（而且他们也急需正确的算法，但他们没有意识到）。 - Dietmar Kühl

5个回答

2

你期望一个节点拥有哪些属性？我期望看到一组可变的属性。任何固定的节点（或边）属性集合可能对某些算法不足够。这促使我开发了我所谓的“数据访问器”，以及在BGL中被称为“属性映射”。使用节点地址来确定图形属性不会让我感到不安，尽管我希望在大多数情况下使用类似索引的东西。根据图形大小是否已知或者图形是即时创建的，使用std::unordered_map<void*, P> 来确定属性值可能更有效。此外，根据算法，只有部分图形可能被访问。

图可以用许多不同的方式表示。像示例中的邻接表就是其中一种。大多数情况下，使用关联列表更好（即，您具有边缘的显式表示，这在具有不同属性的平行边缘的情况下非常重要）。如果没有平行边缘并且图形几乎完整，则可以使用邻接矩阵。使用适当的抽象来运行算法，甚至可以隐含地表示图形。例如，您可以定义一个图形，其中具有索引N和M的节点相邻，如果N和M具有GCD或某个值。

如何表示属性主要取决于算法的需求。给定的节点类型似乎旨在在面向对象的设置中使用，但这很可能会导致性能不佳。鉴于许多有趣的图形算法具有非线性复杂度，快速操作确实很重要。

- Dietmar Kühl

所要求的具体问题是制作一个图的“深拷贝”。仅使用邻居向量是否可能实现？即使节点之间没有区分数据，哈希映射是否足以解决问题？ - Bob John

整个图只包括这些节点吗？还是有一个包含节点列表的“图”对象？如果是后者，那么只需复制图形而不需要任何查找结构就很容易。如果只有这些节点，则可以使用std::unordered_map<void*，X>创建一个“原始节点映射到已复制节点”的映射：指针是哈希容器的完全有效的键。 - Dietmar Kühl

1

在高性能计算文献中，通常使用压缩稀疏行（CSR）格式来表示图形，这种格式也适用于稀疏矩阵计算。许多现实世界的图形（道路地图、社交网络等）都是稀疏的，使用邻接矩阵会浪费空间。对于稀疏图形，CSR格式比邻接列表更具性能优势，因为它需要较少的内存提取。

我为NVIDIA的Parallel Forall博客写了一篇博客文章，其中包括一个图形的样本图片及其在此格式下的表示。请参见“GPU上的稀疏图表示”部分。事实证明，许多基于CPU的HPC图形算法也使用此格式。

总结该文章，请查看以下图形：

_{（来源：nvidia.com）}

(忽略标签 BC[x] = y)

如果我们将顶点从1...9重新编号为0...8，那么可以使用CSR格式表示图形如下：

_{(来源: nvidia.com)}

其中R是行偏移量数组，C是列索引数组。行偏移量数组是一个n+1元素数组，指向每个顶点在列索引数组中的相邻开始和结束位置。例如，顶点u的邻接列表位于从C[R[u]]到C[R[u+1]-1]，包括两端。

对于上面的示例，如果我们查看图形中的顶点4（我们已将其重新编号为顶点3），我们可以看到R [3] = 8和R [4] = 12，这意味着与3相邻的顶点位于C [8]到C [12]之间，或者是顶点{0,2,4,5}，对应于图片中显示的{1,3,5,6}。

- Adam27X

0

你说得对。在图中，如果没有与每个顶点（节点）相关联的任何标识信息，你对图的操作就会受限。

面试官可能是疏忽了这一点，或者他可以通过维护一个将每个节点与一个ID或名称关联起来的映射来进行解释。当信息量很大或者维护成本很高时，他们会选择这种方式。话虽如此，从每个节点指向数据的指针比基于映射的方法更常见。

- KalyanS

0

如果是一个小图，你可以用邻接矩阵来表示它。每个单元格 (i,j) 表示节点 i 与节点 j 相邻。

- aleberguer

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- kamoor · Accepted Answer

这是一种常见的表示图形的方式，尤其在面向对象编程语言中。它非常可扩展，以表示相互连接的数百万个节点。您还可以使用邻接矩阵来表示图形，这对于学习算法和实现样例代码很有用。但这不是表示数百万节点的好方法。

在提供的两种数据结构之间，我会说第二种更实用，因为您总是希望在每个节点中存储某些值。但是在某些情况下，您没有任何要存储的内容，在这种情况下，您也可以很好地使用第一个数据结构。例如，双分图可用于解决最大流问题。

因此，答案应该是“基于您尝试解决的问题”。

使用邻接矩阵解决任何问题都可以使用提供的第一种数据结构来表示。需要更多于顶点和边的数据结构通常属于更高级别的“扩充数据结构”，这是解决大多数实际问题所必需的。

其他参考资料：