如何存储欧拉图结构？

Question

我正在研究Euler路径问题，并发现了一个问题:如何定义或存储Euler图结构？

一种常用的方法是使用“伴随矩阵”，Ci是用来存储i-j之间的边的，它简洁有效！但是，这种矩阵受到两个节点之间的边唯一的情况的限制(图1)。

class EulerPath
{
   int[][] c;//adjoint matrix,c[i][j] means the edge between i and j
}

如果有几个边(图2)呢?我的解决方案可能是使用自定义类，如"Graph“、"Node”、"Edge“来存储图，但是将图划分为一些离散的结构，这意味着我们必须考虑更多的类细节，这可能会损害效率和简洁性。所以我很想听听你的建议！非常感谢！

class EulerPath
{
   class Graph
   {
      Node[] Nodes;
      Edge[] Edges;
   }
   class Node{...}
   class Edge{...}
}

​

​

Answer 1

您可以使用邻接矩阵来存储具有多个边的图。您只需将c[i][j]的值设为顶点i与顶点j相邻的次数。在第一种情况下，是1，在第二种情况下，是3。参见维基百科 --邻接矩阵不是由1和0组成的，这只是简单图邻接矩阵的特例。

编辑:你可以用这样的邻接矩阵来表示你的第二个图：

  1 2 3 4
1 0 3 1 1
2 3 0 1 1
3 1 1 0 0
4 1 1 0 0

Answer 2

至少有三种方法可以做到这一点：

邻接表

意味着您有一个名为alN的2D数组

N这个N是节点索引

alN这个N是邻居节点索引

例如，具有此输入的图形：

0 => 1
1 => 2
2 => 3
3 => 1

邻接列表如下所示：

0 [1]
1 [2,3]
2 [1,3]
3 [1,2]

PS：由于这是一个2D数组，并不是所有的水平单元格都将被使用，所以您需要跟踪每个图形索引的连接邻居的数量，因为一些编程语言用0初始化数组值，这是图中的一个节点索引。这可以很容易地通过创建另一个数组来实现，该数组将计算每个图索引的邻居数。本例示例：numLinks: [1,2,2,2]

矩阵

使用一个矩阵，创建一个NxN2D数组，并将一个1值放置在相邻行节点的交集中：

具有相同输入的示例：

  0 1 2 3
0 0 1 0 0
1 1 0 1 1
2 0 1 0 1
3 0 1 1 0

类节点

最后一个方法是创建一个名为Node的类，它包含一个Node类型的动态数组。并且可以将连接到的其他节点存储在这个数组中。

Answer 3

考虑使用链表的向量。添加一个具有Vertex字段和Weight字段的类(让我们将其命名为Entry)。您的权重最好是另一个向量或链接列表(最好是11)，它将包含到相应的Vertex的所有可能的权重。您的主类将有一个向量向量，或者一个链表向量(我更喜欢链表，因为您很可能不需要随机访问，在执行任何操作时都会被迫遍历每个Entry )。主类将有一个包含所有顶点的向量。在C++中，这看起来如下所示：

class Graph{
    std::vector<std::forward_list<Entry>> adj_list;
    std::vector<Vertex> vertices;
};

其中，对应于Vertex的vertices[i]在adj_list[i]中有相应的列表。因为每个Entry都包含与您所连接的Vertex有关的信息以及相应的权重，所以您将得到这个类表示的图形。