algorithm - 对称矩阵和非对称矩阵的区别

Question

我正在练习图形和邻接矩阵。但我找不到区分对称矩阵和非对称矩阵的好例子。谁能告诉我如何区分对称矩阵或非对称矩阵。

Answer 1

如果邻接矩阵是从无向图导出的，则它是对称的。

这意味着，来自节点 A -> B 的路径与来自节点的路径具有相同的成本/权重/长度B -> A。

如果您创建邻接矩阵M，它将是对称的，这意味着对于任何i和j，M[i][j] == M[j]i]。从数学上讲，矩阵与其转置相同。因此，如果您转置矩阵，它将看起来完全一样。从图形上看，这样的矩阵如下所示：

0 2 3 4
2 0 5 6
3 5 0 7
4 6 7 0

由于对称性，您通常可以使用更少的内存来表示它。对于无向图上的Floyd-Warshall 算法等算法，您可以将计算量减少 50%，因为您只需要计算一半的矩阵：

0 2 3 4
  0 5 6
    0 7
      0

为了比较，一个非对称矩阵：

0 2 3 9 <--
2 0 5 6
3 5 0 7
4 6 7 0

请注意，它与前面的示例几乎相同，但在右上角，有一个9. 因此，不再可能沿矩阵的对角轴镜像矩阵。

Answer 2

您可以检查对称图的示例