algorithm - 如何存储欧拉图结构？

Question

我正在解决欧拉路径问题并发现了一个问题:如何定义或存储欧拉图结构？

通常的做法是使用“伴随矩阵”，定义C[i][j]来存储i-j之间的边，简洁有效!但是这种矩阵受限于2之间的边的情况节点是唯一的(图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。另请参阅 Wikipedia -- 邻接矩阵并不定义为仅由 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