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

Question

我在解决 Euler Path 问题时发现了一个问题:How to define or store a Euler graph struct?

通常的做法是使用“伴随矩阵”，定义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