algorithm - 为什么图算法会引用之前的边？

Question

几乎所有与路径相关的图算法似乎都使用一种模式，该模式涉及保存用于到达当前顶点的边。相反，为什么当前顶点不持有对下一条边的任何引用，类似于链表？我猜你可以，但权衡是什么？

Answer 1

的确，这里有几个混杂的概念。首先，我将介绍图形数据结构。

图形表示

数据结构是一种构建数据的方式(好吧，这个很简单)。这就是您的图表在内部表示的方式。而且还有很多可能性。

如果您稍微考虑一下，图中有两个中心概念:边和顶点。您选择如何存储它们完全取决于您。为了便于解释，我将考虑为顶点指定一个从 0 到 V-1 的唯一编号。

周围有几种表示法，根据您的问题，一种可能比另一种更合适。基本上，顶点和边之间存在冗余信息，因此为两者创建一个结构是多余的。我现在将讨论这两种情况。

您可以显式创建显式顶点结构。每个顶点都包含一个它也可以去的顶点列表。 Graph 结构应该维护一个包含所有 Vertices 的数组，以使其高效。这是您所指的结构，并且是有效的结构。

在这种情况下，边是隐式的:如果一个顶点可以到达另一个顶点，那么两者之间就有一条边。但是，没有创建边结构，它由每个顶点中包含的列表暗示。

第二种可能，创建一个边缘结构。每条边包含它的起点和终点(它们是顶点，可以表示为整数)。 Graph 数据结构包含一个数组，并且对于每个槽，存储从该顶点开始(或结束)的所有边的列表。

同样，这是一个有效的数据结构，通常称为邻接表表示。而这一次，没有明确的顶点结构:它们是包含在边中的整数。

使用显式边(和隐式顶点)，还有邻接矩阵表示，如果图很稠密，它会很方便。

最后，选择图的表示形式是关于哪种最适合您的情况，以及您更了解哪种，但没有绝对的规则。

在我的例子中，我很快就理解了邻接表，但是我很难理解第一个表示，所以你应该选择你更熟悉的那个。

图算法

现在是算法。这个想法是，给定一个 Graph 结构(无论后面是哪种表示)，它提供了一些定义的函数，处理这个 Graph 以获得关于它的一些信息。

在 DFS/BFS 的情况下，搜索的信息是遍历图从一个源顶点到每个可到达的顶点。的确，对于那些算法，每个顶点都与他的前任之一相关联。

那是因为我们想从这些算法中得到的信息是获取从源点到另一个顶点的路径中的一个。当然还有其他的路径，但这并不重要。

事实上，找到从一个顶点到所有其他顶点的所有可能路径是一个 NP 完全问题，有时甚至是不可能的(例如，如果存在循环)。

这就是为什么只存储顶点的前导:因为我们想要的只是一个路径，它使这些算法在空间和内存方面都高效。

我希望这能回答您的问题并清除您的想法。