0

我一直在阅读有向图。我已经设法让抽象图形数据类型在我的应用程序中工作，但我觉得它不是特别直观，并且正在考虑用普通的多维数组替换它。

我的图是稀疏且无环的。每个顶点都可以从一个特定的“主”顶点到达。如果它是一棵树，这个主顶点将是“根”。这是一个社交网络，这个主顶点将是“我”。

尽管我的图可能有数十万个顶点，但它的深度是有限的：任何两个节点之间的最大距离是 3 条边。

底层数据表示是一个邻接表。一个小例子如下所示：

Head | Tails
--------------
  1  | 2, 3, 4
  2  | 5  
  3  | 5
  4  | 5
  5  | 6

如果我使用普通的多维数组而不是我的图形数据类型，它看起来像这样：

$me[1][2][5][6]
$me[1][3][5][6]
$me[1][4][5][6]

现在，我希望能够用这张图做的主要事情是：

  1. 将其作为层次结构进行导航。我意识到一些子顶点将具有多个类别（例如＃5），但这就是我想要的这个特定用例。在这一点上，我看不出数组和图表之间有任何真正的区别。
  2. 将其布置为列表（按字母顺序，根据顶点名称），没有重复。我可能会做一个 DFS，边走边标记访问过的顶点，以避免多次探索它们。但据我所知，这可以使用图形或数组来实现，并且成本相同。
  3. 对任何给定的点对进行“所有路径”分析。因为我想要“所有路径”（即，我不只是检查可达性），所以在我看来，我必须遍历整个图表，而且我再次看不出图表优于数组。

我觉得我错过了一些东西，但我不能把手指放在它上面。你能？？？任何想法，建议，见解或建议都非常感谢......（顺便说一下，我使用的是 PHP，数据源是一个关系数据库。我认为这没有任何真正的区别）。

谢谢！

4

2 回答 2

2

您需要了解的一件事是，有向图（或有向图）是一个概念，而关联数组是一种数据结构。

digraph 概念的一个实例可以存储在许多不同的数据结构中，您可以在此维基百科页面上找到最常见的数据结构。

我不确定你在用你的多维数组做什么......存储所有路径？你最终会得到 N³ 的空间复杂度，并且很难构建它。基于树的结构至少会更有效。

现在到你想用你的图表做的事情：

  1. 作为层次结构导航。基本的有向图概念不允许在层次结构中上升，但您也可以轻松存储反向图（尤其是基于矩阵的表示，只需使用 3 个值而不是 2 - 向前、向后和什么都没有）。
  2. 根据 name 将其作为列表列出。您必须将名称存储在某处（在侧面地图或顶点对象中），但它不应该比根据名称对其他任何内容进行排序更难。
  3. 进行“所有路径”分析。您可能可以通过 DP 和路径的共享表示来摆脱线性复杂性（路径数量）。
于 2013-01-17T14:45:19.363 回答
0

看来你的数据结构太复杂了。如果将有向图表示为多维数组，它几乎总是二维的，因此

$array[$x][$y]

是一个布尔值，当且仅当图中存在从节点 $x 到节点 $y 的边时为 TRUE。在你的例子中，如果是例如

$array[1][2] = TRUE
$array[1][5] = FALSE

但是对于稀疏图，使用这种布尔矩阵表示通常不是很好。通常你会有一个一维数组，将每个节点映射到一组有边的节点，例如

$array[1] = { 2, 3, 4 }

其中 { ... } 表示某种无序集合数据结构，例如可以是二叉搜索树或哈希集（哈希表）。

这种数据结构使您能够快速找到从给定节点到有弧的节点，这是图算法的一个关键特性。

有时您还希望能够向后遍历您的图表；在这种情况下，您将拥有另一个将节点映射到其前任列表的数组。

于 2013-01-17T13:11:27.753 回答